互不侵犯

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=11; 
 5 const int maxm=2007;
 6 int n,al,num;
 7 int sta[maxm],sum[maxm];
 8 long long f[maxn][maxm][maxm];
 9 void maketable(int st,int su,int node){
10     if(node>=n){
11         sta[++num]=st;
12         sum[num]=su;
13         return;
14     }
15     maketable(st,su,node+1);
16     maketable(st+(1<<node),su+1,node+2);
17 }
18 int main(){
19     cin>>n>>al;
20     maketable(0,0,0);
21     for(int i=1;i<=num;i++)
22         f[1][i][sum[i]]=1;
23     for(int i=2;i<=n;i++){
24         for(int j=1;j<=num;j++){
25             for(int k=1;k<=num;k++){
26                 if(sta[j]&sta[k]) continue;
27                 if(sta[j]&(sta[k]<<1)) continue;
28                 if((sta[j]<<1)&sta[k]) continue;
29                 for(int s=al;s>=sum[j];s--){
30                     f[i][j][s]+=f[i-1][k][s-sum[j]];
31                 }
32             }
33         }
34     }
35     long long ans=0;
36     for(int i=1;i<=num;i++) ans+=f[n][i][al]; 
37     cout<<ans<<endl;
38     return 0;
39 }