解题思路:
对于这种在每一输入都有固定答案并且当前结果受前结果影响的情况下,动态规划是很好的选择;
对于这道题来看,假设输入的N为i,2*N 的画布中有多少组合其实是受到 i-1 或者输入数 i 前任意一种输入影响的,因此只需要找到转移方程就好。
1⃣️先关注竖状基本积木:压缩后竖状积木只能构成两种组合:第一种就是单独的一个方块记为1,第二种就是一个由两个横着的1构成的0.5+0.5的一个方块
2⃣️再到直角状基本积木:压缩后很显然就是1.5的方块,但1.5不能构成完整的方块,因此在构成时还要随着空间的变大变成1.5+1.5的三个方块
所以对于dp[i],就可以由dp[i-1]*竖状积木的变化情况 + 由于空间变大的dp[i-3]*直角状积木的变化情况,再取模就好
因此转移方程如下:
dp[i] = (dp[i-1]*2%mod + dp[i-3]%mod)%mod
最后:还要记得初始化dp[1], dp[2], dp[3]并且循环头要从4开始,不然的话当dp[i-3]的时候就会取dp的末尾值导致混乱
完整代码如下:
n = int(input()) dp = [0]*(n+1) mod = 1e9+7 dp[1], dp[2], dp[3] = 1, 2, 5 for i in range(4, n+1): dp[i] = (dp[i-1]*2%mod + dp[i-3]%mod)%mod print(int(dp[n]))
0.0分
5 人评分
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:495 |
Pascal三角 (C语言代码)格式错误浏览:520 |
用筛法求之N内的素数。 (C语言代码)浏览:803 |
母牛的故事 (C语言代码)浏览:549 |
1113题解浏览:785 |
A+B for Input-Output Practice (V) (C语言代码)浏览:463 |
罗列完美数 (C语言代码)浏览:491 |
矩形面积交 (C语言代码)浏览:1304 |
判定字符位置 (C语言代码)浏览:794 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:465 |