「SCOI2005」互不侵犯

题解：here
AC_Code:
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2000;
 5 
 6 int sit[maxn],gs[maxn];
 7 int n,k,cnt;
 8 ll dp[10][maxn][100];
 9 
10 void dfs(int he,int sum,int node){
11     if( node>=n ){
12         sit[++cnt]=he;
13         gs[cnt]=sum;
14         return ;
15     }
16     dfs(he,sum,node+1);
17     dfs(he+(1<<node),sum+1,node+2);
18 }
19 
20 int main()
21 {
22     cin>>n>>k;
23     dfs(0,0,0);
24     for(int i=1;i<=cnt;i++) dp[1][i][gs[i]]=1;//因为dfs本来就是按行的情况来弄得,所以在第一行,所有状态都有一种情况
25     for(int i=2;i<=n;i++){
26         for(int j=1;j<=cnt;j++){
27             for(int u=1;u<=cnt;u++){
28                 if( sit[j]&sit[u] ) continue;
29                 if((sit[j]<<1)&sit[u]) continue;
30                 if(sit[j]&(sit[u]<<1)) continue;
31                 for(int s=k;s>=gs[j];s--){
32                     dp[i][j][s]+=dp[i-1][u][s-gs[j]];
33                 }
34             }
35         }
36     }
37     ll ans=0;
38     for(int i=1;i<=cnt;i++) ans+=dp[n][i][k];
39     cout<<ans<<endl;
40     return 0;
41 }