暴力dp版

/*
f[i][x1][x2][x3]：表示第i-1行填x1，第i行填x2，第i+1填x3的方案数（x1、x2、x3为：0或1） 
*/

#include<bits/stdc++.h>
using namespace std;
int a[11100];
long long f[11100][2][2][2];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,0,sizeof(f));
    if(a[1]==0)      f[1][0][0][0]=1;
	else if(a[1]==1) f[1][0][1][0]=1,f[1][0][0][1]=1;
    else if(a[1]==2) f[1][0][1][1]=1;
    for(int i=2;i<=n;i++)
    {
    	if(a[i]==0) 
		    f[i][0][0][0]=f[i-1][0][0][0]+f[i-1][1][0][0];
    	else 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];
    	}
    	else if(a[i]==2)
    	{
    		f[i][0][1][1]=f[i-1][0][0][1]+f[i-1][1][0][1];
    		f[i][1][0][1]=f[i-1][0][1][0]+f[i-1][1][1][0];
    		f[i][1][1][0]=f[i-1][0][1][1]+f[i-1][1][1][1];
    	}
    	else if(a[i]==3)
    	{
    		f[i][1][1][1]=f[i-1][0][1][1]+f[i-1][1][1][1];
    	}
    }
    long long ans=0;
    /*这样是错的，因为第n+1行不存在（不能为1），如果a[n]=1或2，不能依赖第n+1行为1 
	for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)ans+=f[n][i][j][k];
    */ 
	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 if(a[n]==2)ans+=f[n][1][1][0];
	printf("%lld\n",ans);
    return 0;
}

状态压缩版

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N], dp[N][10];
int calc(int x){
    int res=0;
    for(int i=x; i>=1; i-=i&-i) res++;
    return res;
}
int main(){
    //freopen("a.in", "r", stdin);
    int n, ans=0; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(dp, 0, sizeof(dp));
    dp[1][0]=dp[1][4]=1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<(1<<3)-1; j++){
            if(calc(j>>1)<=a[i] && calc(j)==a[i-1]){
                dp[i][j]+=dp[i-1][(j<<1)%8]+
                dp[i-1][((j<<1)%8)|1];
            }
        }
    }
    for(int i=0; i<(1<<3)-1; i++){
        if((calc(i>>1)==a[n]) && (n==1 || calc(i)==a[n-1]))
            ans+=dp[n][i];
    }
    printf("%d\n", ans);
    return 0;
}

暴力dp版：

/*
f[i][x1][x2][x3]：表示第i-1行填x1，第i行填x2，第i+1填x3的方案数（x1、x2、x3为：0或1） 
*/

#include<bits/stdc++.h>
using namespace std;
int a[11100];
long long f[11100][2][2][2];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,0,sizeof(f));
    if(a[1]==0)      f[1][0][0][0]=1;
	else if(a[1]==1) f[1][0][1][0]=1,f[1][0][0][1]=1;
    else if(a[1]==2) f[1][0][1][1]=1;
    for(int i=2;i<=n;i++)
    {
    	if(a[i]==0) 
		    f[i][0][0][0]=f[i-1][0][0][0]+f[i-1][1][0][0];
    	else 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];
    	}
    	else if(a[i]==2)
    	{
    		f[i][0][1][1]=f[i-1][0][0][1]+f[i-1][1][0][1];
    		f[i][1][0][1]=f[i-1][0][1][0]+f[i-1][1][1][0];
    		f[i][1][1][0]=f[i-1][0][1][1]+f[i-1][1][1][1];
    	}
    	else if(a[i]==3)
    	{
    		f[i][1][1][1]=f[i-1][0][1][1]+f[i-1][1][1][1];
    	}
    }
    long long ans=0;
    /*这样是错的,因为第n+1行不存在（不能为1），如果a[n]=1或2，不能依赖第n+1行为1 
	for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)ans+=f[n][i][j][k];
    */ 
	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 if(a[n]==2)ans+=f[n][1][1][0];
	printf("%lld\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N], dp[N][10];
int calc(int x){
    int res=0;
    for(int i=x; i>=1; i-=i&-i) res++;
    return res;
}
int main(){
    //freopen("a.in", "r", stdin);
    int n, ans=0; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(dp, 0, sizeof(dp));
    dp[1][0]=dp[1][4]=1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<=(1<<3)-1; j++){
            if(calc(j>>1)<=a[i] && calc(j)==a[i-1]){
                dp[i][j]+=dp[i-1][(j<<1)%8]+
                dp[i-1][((j<<1)%8)|1];
            }
        }
    }
    for(int i=0; i<=(1<<3)-1; i++){
        if((calc(i>>1)==a[n]) && (n==1 || calc(i)==a[n-1]))
            ans+=dp[n][i];
    }
    printf("%d\n", ans);
    return 0;
}