FC背包DP蓝桥杯2022-G 积木画
作者:
小花猪
,
2023-03-10 00:01:34
,
所有人可见
,
阅读 160
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7 + 10, mod = 1000000007;
/*g[i][j]表示i状态能否向j状态转换*/
int g[4][4] = {
//00,01,10,11状态(二进制)
{1, 1, 1, 1},//对应f[i][j]第i列排满后i+1列的状态是00(上下都没有填充)
{0, 0, 1, 1},//对应f[i][j]第i列排满后i+1列的状态是01(上都没有填充)
{0, 1, 0, 1},//对应f[i][j]第i列排满后i+1列的状态是10(下都没有填充)
{1, 0, 0, 0}//对应f[i][j]第i列排满后i+1列的状态是11(上下都有填充)
};
int f[N][4];//f[i][j]第i-1列排满后i列的状态是j的方案数
int main()
{
int n;
cin >> n;
f[1][0] = 1;//只有一列的时候只能是j=0的情况(上下都没有填充)
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < 4; j ++ )
for (int k = 0; k < 4; k ++ ){
//第i+1列是k情况的填充总数(在第i列中遍历0~j种情况)
f[i + 1][k] = (f[i + 1][k] + f[i][j] * g[j][k]) % mod;
}
cout<<f[n + 1][0]<<endl;
// for (int i = 1; i <= n+1; i ++ ){
// printf("%d:",i);
// for (int j = 0; j < 4; j ++ ){
// printf("% 4d",f[i][j]);
// }
// cout<<endl;
// }
return 0;
}