题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1088
记录下每一个格子对应左边格子放的雷的情况，然后dp转移就好了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 int inline readint(){ 7 int Num;char ch; 8 while((ch=getchar())<'0'||ch>'9');Num=ch-'0'; 9 while((ch=getchar())>='0'&&ch<='9') Num=Num*10+ch-'0'; 10 return Num; 11 } 12 int N; 13 int a[10010]; 14 ll f[10010][2][2][2]; 15 int main(){ 16 N=readint(); 17 for(int i=1;i<=N;i++) a[i]=readint(); 18 f[0][0][0][0]=1; 19 f[0][0][0][1]=1; 20 for(int i=1;i<=N;i++){ 21 switch(a[i]){ 22 case 0: 23 f[i][0][0][0]=f[i-1][1][0][0]+f[i-1][0][0][0]; 24 break; 25 case 1: 26 f[i][1][0][0]=f[i-1][1][1][0]+f[i-1][0][1][0]; 27 f[i][0][1][0]=f[i-1][1][0][1]+f[i-1][0][0][1]; 28 f[i][0][0][1]=f[i-1][1][0][0]+f[i-1][0][0][0]; 29 break; 30 case 2: 31 f[i][1][1][0]=f[i-1][1][1][1]+f[i-1][0][1][1]; 32 f[i][1][0][1]=f[i-1][1][1][0]+f[i-1][0][1][0]; 33 f[i][0][1][1]=f[i-1][1][0][1]+f[i-1][0][0][1]; 34 break; 35 case 3: 36 f[i][1][1][1]=f[i-1][1][1][1]+f[i-1][0][1][1]; 37 break; 38 } 39 } 40 ll ans=f[N][1][1][0]+f[N][1][0][0]+f[N][0][1][0]+f[N][0][0][0]; 41 printf("%lld ",ans); 42 return 0; 43 }