AcWing 4406. 积木画 dp详细注解
原题链接
中等
作者:
灰小白
,
2022-05-31 21:31:15
,
所有人可见
,
阅读 285
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 1e7 + 10 , MOD = 1000000007;
int dp[N][4];
int main()
{
int n;
cin >> n ;
//dp[1][0] = 0 ;dp[1][3] = 1;
// 1 表示当前位置有积木,0 表示没有。dp[i][j] 长度为 i 的两个位置状态
// dp[i][0] 0 dp[i][1] 1 dp[i][2] 0 dp[i][3] 1
// 0 0 1 1
dp[2][3] = 2 ,dp[2][0] = 1 ;
dp[2][0] = dp[2][1] = dp[2][2] = 1 ;
for(int i = 3 ; i <= n ; i++){
// 1、这里要注意,dp[i - 1][0]可变为dp[i - 1][3]再到 dp[i][3] ,这里会重复。所以只记录下面的情况
// 或者通过两个横木变为 dp[i][3]
// 2、因为MOD很大,所以两两相加取模,不然会爆 int 。
dp[i][3] = ((dp[i - 1][1] + dp[i - 1][2]) % MOD + (dp[i - 1][0] + dp[i - 1][3]) % MOD ) % MOD;
dp[i][2] = (dp[i - 1][1] + dp[i - 1][0]) % MOD;
dp[i][1] = (dp[i - 1][2] + dp[i - 1][0]) % MOD;
dp[i][0] = dp[i - 1][3] ;
}
cout << dp[n][3] << endl;
return 0;
}
写的非常好,想法和我一摸一样,但是我那个重复的没有去掉,大意了