状压输出为0求调
查看原帖
状压输出为0求调
742017
zhangxiao666楼主2024/1/26 21:03
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, num;
int a[2050], cnt[2050];
int dp[10][100][2050];

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for(int i = 0; i < (1 << n); i++)
    {
        int tot = 0, now = i;
        while(now)
        {
            tot += (now & 1);
            now >>= 1;
        }
        if(((i << 1) & i) && ((i >> 1) & i) == 0)
        {
            num++;
            a[num] = i;
            cnt[i] = tot;
        }
    }
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= num; j++)
        {
            int now = a[j];
            for(int l = 1; l <= num; l++)
            {
                int last = a[l];
                if(((now << 1) & last) == 0 && (now & last) == 0 && ((now >> 1) & last) == 0)
                {
                    for(int sum = cnt[now]; sum <= k; j++)
                    {
                        dp[i][sum][now] += dp[i - 1][sum - cnt[now]][last];
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= num; i++) ans += dp[n][k][a[i]];
    cout << ans;
    return 0;
}
2024/1/26 21:03
加载中...