Miku

真是自闭呢

这个题还是还理解的

dfs预处理出每一行的情况，然后dp

#include<iostream>
#include<cstdio>
using namespace std;
int ok[2001];
int n,kk;
long long dp[10][2001][2001];
int cou[2001];
int si[2001];
int cnt;
void dfs(int p,int co,int ns){
//  cout<<p<<endl;
    if(p>n){
        cnt++;
        ok[cnt]=ns;
        cou[cnt]=co;
        return ;
    }
    dfs(p+1,co,ns);
    dfs(p+2,co+1,ns+(1<<p));
    return ;
}
long long ans;
int main(){
    scanf("%d%d",&n,&kk);
    dfs(1,0,0);
    for(int i=1;i<=cnt;++i)
    {
        dp[1][i][cou[i]]=1;
    }
    for(int i=2;i<=n;++i){
        for(int j=1;j<=cnt;++j){
            for(int k=1;k<=cnt;++k){
                if((ok[j]&ok[k])==0){
                    if(((ok[j]<<1)&ok[k])==0){
                        if(((ok[j]>>1)&ok[k])==0){
                            for(int z=kk;z>=cou[j];z--){
                                dp[i][j][z]+=dp[i-1][k][z-cou[j]];
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=cnt;++i){
        ans+=dp[n][i][kk];
    }
    cout<<ans;
    return 0;