WA,求大佬帮忙
查看原帖
WA,求大佬帮忙
716615
cmjy楼主2024/4/10 00:46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10, M = 1<<11;

ll num[N*N];
bool st[M]; 
ll dp[N][M][N*N];
int n,g;

void isvalid(int m){
    for(int i = 0; i < m; ++i){
        if((i & (i << 1)) || (i & (i >> 1))) continue;
        int cnt = 0;
        for(int j = 0; j < n; ++j){
            if(i & (1 << j)) cnt++;
        }
        st[i] = true; // 记录合法状态 
        num[i] = cnt; // 记录状态i的国王数 
    }
}

int main(){
    scanf("%d %d", &n, &g);
    if(g == 0){
        cout << 1;
        return 0;
    }
    int m = 1 << n;
    isvalid(m);
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < m; ++j){
            if(!st[j]) continue;
            int s1 = num[j];
            for(int k = 0; k < m; ++k){
                if(!st[k]) continue;
                int s2 = num[k];
                if((j & k) == 0 && ((j & (k << 1)) == 0) && ((j & (k >> 1)) == 0)){
                    for(int x = s1; x <= g; ++x){
                        if(x - s1 >= 0) dp[i][j][x] += dp[i - 1][k][x - s1]; // 类似背包 
                    }
                }
            }
        }
    }
    ll res = 0;
    for(int i = 1; i < m; ++i){
        res += dp[n][i][g];
    }
    printf("%lld", res);
    return 0;
}

2024/4/10 00:46
加载中...