输入输出格式
输入格式：
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）
输出格式：
一个数，即第一列中雷的摆放方案数。
输入输出样例
输入样例#1： 复制
2
1 1
输出样例#1： 复制
2
借鉴了一个大神的思路，这道题我用的四维dp。
用四维数组f储存
一维第二列位置，二维三维四维存i-1，i，i+1是否有雷
初始化：f[0][0][0][0]=f[0][0][0][1]=1; 就是第一个地方有雷或无雷两种情况。
用四维数组f储存
一维第二列位置，二维三维四维存i-1，i，i+1是否有雷
初始化：f[0][0][0][0]=f[0][0][0][1]=1;
如果a[i]为0
f[i][0][0][0]=f[i-1][0][0][0]+f[i-1][1][0][0];
f[i][1][0][0]=f[i-1][0][1][0]+f[i-1][1][1][0];
f[i][0][1][0]=f[i-1][0][0][1]+f[i-1][1][0][1];
f[i][0][0][1]=f[i-1][0][0][0]+f[i-1][1][0][0];
如果为2 f[i][1][1][0]=f[i-1][0][1][1]+f[i-1][1][1][1];
f[i][1][0][1]=f[i-1][0][1][0]+f[i-1][1][1][0];
f[i][0][1][1]=f[i-1][0][0][1]+f[i-1][1][0][1];
如果为3
f[i][1][1][1]=f[i-1][0][1][1]+f[i-1][1][1][1]
然后如果a[n]=1
ans=f[n][1][0][0]+f[n][0][1][0];
因为n+1就没有了
所以肯定四维为0
如果a[n]=2
ans=f[n][1][1][0];
如果a[n]=3
肯定无解
如果a[n]=0
ans=f[n][0][0][0]
输出ans
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
int n,f[maxn][2][2][2],ans,a[maxn];
int main(){scanf("%d",&n);for(register int i=1;i<=n;i++){scanf("%d",&a[i]);}f[0][0][0][0]=f[0][0][0][1]=1; //初始化for(register int i=1;i<=n;i++){if(a[i]==0)f[i][0][0][0]=f[i-1][1][0][0]+f[i-1][0][0][0];if(a[i]==3)f[i][1][1][1]=f[i-1][0][1][1]+f[i-1][1][1][1];if(a[i]==2){f[i][1][1][0]=f[i-1][0][1][1]+f[i-1][1][1][1];f[i][1][0][1]=f[i-1][0][1][0]+f[i-1][1][1][0];f[i][0][1][1]=f[i-1][0][0][1]+f[i-1][1][0][1];}if(a[i]==1){f[i][1][0][0]=f[i-1][0][1][0]+f[i-1][1][1][0];f[i][0][1][0]=f[i-1][0][0][1]+f[i-1][1][0][1];f[i][0][0][1]=f[i-1][0][0][0]+f[i-1][1][0][0];}}if(a[n]==0) ans=f[n][0][0][0]; //判断else if(a[n]==1) ans=f[n][1][0][0]+f[n][0][1][0];else ans=f[n][1][1][0];printf("%d",ans);
}
