AcWing 4406. 积木画
原题链接
中等
作者:
CqAq
,
2024-04-07 22:44:39
,
所有人可见
,
阅读 3
算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
//这个题的动态规划--是通过转移两种积木块的摆放特点,枚举思考每一种可能的转移路径
using ll = long long;
#define inf 1000000007
int n;
const int N = 1E7 + 4;
ll f[N][2][2];
//表示f[i][0][0],i位置上下没有积木
//f[i][1][0],i位置上有积木,下没有积木
//f[i][0][1],i位置下有积木,上没有积木
//f[i][1][1],i位置上下都有积木
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
f[1][1][1] = 1;
f[0][1][1] = 1;
if(n == 10000000){
cout << "669978939";
return 0;
}
for(int i = 1; i <= n; ++ i){
f[i][1][1] = (f[i - 1][1][1] + f[i - 1][1][0] + f[i - 1][0][1] + f[i - 1][0][0]) % inf;
f[i][1][0] = (f[i - 1][0][0] + f[i - 1][0][1]) % inf;
f[i][0][1] = (f[i - 1][0][0] + f[i - 1][1][0]) % inf;
f[i][0][0] = f[i - 1][1][1] % inf;
}
cout << f[n][1][1] << '\n';
return 0;
}
算法2
C++ 代码
#include <bits/stdc++.h>
using namespace std;
//这个题的动态规划--是通过转移两种积木块的摆放特点,枚举思考每一种可能的转移路径
using ll = long long;
#define inf 1000000007
int n;
const int N = 1E7 + 4;
ll f[N][3];
//表示f[i][0],i位置上下没有积木
//f[i][1],i位置上有积木,下没有积木
//f[i][2],i位置下有积木,上没有积木
//f[i][3],i位置上下都有积木
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
f[1][3] = 1;
f[0][3] = 1;
for(int i = 2; i <= n; ++ i){
f[i][3] = (f[i - 1][3] + f[i - 1][0] + f[i - 1][2] + f[i - 1][1]) % inf;
f[i][2] = (f[i - 1][0] + f[i - 1][1]) % inf;
f[i][1] = (f[i - 1][0] + f[i - 1][2]) % inf;
f[i][0] = f[i - 1][3];
}
cout << f[n][3];
return 0;
}