1 条题解

  • 1
    @ 2026-7-19 15:43:51
    # include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=1e3+5;
    const int INF=0x3f3f3f3f;
    int n,k,ans;
    int state[N],len;
    int num[N];
    int dp[10][1000][100];
    int getNum(int x){
    	int sum=0;
    	while(x){
    		sum++;
    		x-=(x&-x);
    	}
    	return sum;
    }
    void init(){
    	for(int i = 0;i<(1<<n);i++){
    		if(!(i&(i<<1))){
    			state[++len]=i;
    			num[len]=getNum(i);
    			dp[1][len][num[len]]=1;
    		}
    	} 
    }
    signed main(){
    	cin>>n>>k;
    	init();;
    	for(int i = 2;i<=n;i++){
    		for(int j = 1;j<=len;j++){
    			for(int l = 1;l<=len;l++){
    				int x=state[j],y=state[l];
    				if((x&y)||(x&(y<<1))||(x&(y>>1)))continue;
    				for(int z = 0;z<=k-num[j];z++){
    					dp[i][j][z+num[j]]+=dp[i-1][l][z];
    				}
    			}
    		}
    	}
    	for(int i = 1;i<=len;i++)
    		ans+=dp[n][i][k];
    	cout<<ans;
    	return 0; 
    }
    
    • 1

    信息

    ID
    3576
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    18
    已通过
    12
    上传者