zoj 3738 Buy the Pets(人、猫、犬DP)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5120
N人がペットを买うことがあって、M匹の猫とP匹の犬がいて、人の番号は1～Nで、猫の番号はN+1～N+Mで、犬の番号はN+M+1～N+M+Pです;誰もが猫と犬を買った.
それからQ条の制限があって、対応する番号の人と猫(アレルギー)あるいは猫と犬(けんか)がいっしょにいられないことを表明して、それからどれだけの买い方がN人を満足させることができて、いわゆる満足はこの人が买った猫と犬がけんかしないで、同时に人は买った猫に対してアレルギーを作らないことです.
dp[i][j]は、i番目の個人のj番目の状態を取ったときのシナリオ数を表す.現在、猫と犬が2次元で圧縮されているものをいくつか取りました.
1240MS.さらに10 MSのより優れた解法もある.

#include<bits/stdc++.h>   
using namespace std;  
int x[45][45];  
long long dp[2][(1<<21)];   
int main(){  
   int n,m,p,a,b,nn;  
   while(~scanf("%d %d %d",&n,&m,&p)){  
       memset(x,0,sizeof(x));  
       scanf("%d",&nn);  
       while(nn--){  
           scanf("%d %d",&a,&b);  
           x[a][b]=1;x[b][a]=1;
       }  
       for(int i=0;i<(1<<(m+p));++i)
           dp[0][i]=0;
       //   memset(dp[0],0,(1<<(m+p)))   ？ 
       dp[0][0]=1;  
       int q=1;  
       for(int i=1;i<=n;i++){  
           for(int j=0;j<(1<<(m+p));++j)
               dp[q][j]=0; 
           for(int j=0;j<(1<<(m+p));++j){  
               if(dp[1-q][j]==0)  
                   continue;  
               for(int k=0;k<m;k++){  
                   if(x[i][n+(k+1)]||(j&(1<<k))) //        j          
                       continue;  
                   for(int l=m;l<m+p;l++){  
                       if(x[n+(k+1)][n+(l+1)]||j&(1<<l)||j+(1<<k)+(1<<l)>=(1<<(m+p)))  //        j          
                           continue;  
                       dp[q][j+(1<<k)+(1<<l)]+=dp[1-q][j]; 
                   }  
               }  
           }  
           q=1-q;  
       }  
       long long ans=0;  
       for(int j=0;j<(1<<(m+p));j++)  
           ans+=dp[1-q][j];  
       printf("%lld
",ans);  
   }  
   return 0;  
}