AcWing 4406. 积木画
原题链接
中等
作者:
mjd
,
2023-03-13 13:08:43
,
所有人可见
,
阅读 206
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10, MOD = 1e9 + 7;
int n;
int g[4][4] = {
{1, 1, 1, 1},
{0, 0, 1, 1},
{0, 1, 0, 1},
{1, 0, 0, 0},
};
//f[i][j], 表示前i - 1列已经摆好,不用管了
//正在摆第i列,状态为j的方案数
//表示有N列,每列有四个状态
int f[N][4];
int main(){
scanf("%d", &n);
//第1列,状态是0,那么有1
f[1][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 4; j++){
for(int k = 0; k < 4; k++){
//第1列一开始就只有一种情况,必然全为0
//能到某一种状态的情况,肯定不止一种,所以要遍历g[j][k],看一下是否能从g[i][j]到g[i][k];
f[i + 1][k] = (f[i + 1][k] + f[i][j] * g[j][k]) % MOD;
}
}
}
printf("%d", f[n + 1][0]);
return 0;
}
每一个{}里面代表可以转移且使第i列完全填充的状态
大佬,这个数组初始化第五行那里看不懂。可以解释一下嘛
是{1,0,0,0}吗
是的,后面两个为啥是0,0呢
我们一开始就是为了让第i列全部填充,那么如果一开始第i列就已经是全部填充,所以也就不用转移到其他任何一种状态
多谢,我还得再看看