洛谷 P1896 [SCOI2005]互不侵犯（状压dp）

传送门

解题思路

用dp[i][j][k]表示到了第i行，第i行状态为j，一共放了k个国王的方案数。

枚举行、本层状态、上层状态、国王数，进行转移。

其中用一个函数求出一个数的二进制有几个一（即这一行放了几个国王）。

初始化时要单独第一行。

注意没开longlong只有70pts。

AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 long long dp[10][520][85],n,kk,ans;
 8 int work(long long x){
 9     int ans=0;
10     while(x>0){
11         ans+=(x&1);
12         x>>=1;
13     }
14     return ans;
15 }
16 int main()
17 {
18     cin>>n>>kk;
19     for(int i=0;i<=(1<<n)-1;i++){
20         if(i&(i>>1)) continue;
21         dp[1][i][work(i)]=1;
22     }
23     for(int h=2;h<=n;h++){
24         for(int i=0;i<=(1<<n)-1;i++){
25             if(i&(i>>1)) continue;
26             int qaq=work(i);
27             for(int j=0;j<=(1<<n)-1;j++){
28                 if((j&(j>>1))||(j&i)||(j&(i<<1))||(j&(i>>1))) continue;
29                 for(int k=qaq;k<=kk;k++){
30                     dp[h][i][k]+=dp[h-1][j][k-qaq];
31                 }
32             }
33         }
34     }
35     for(int i=0;i<=(1<<n)-1;i++) ans+=dp[n][i][kk];
36     cout<<ans<<endl;
37     return 0;
38 }