hdu_4529_郑厂长系列故事——N骑士问题(状压DP)

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4529

题意：中文，不解释

题解：状压DP，dp[i][j][k][s]表示第i行当前用了j个骑士，i-1行的压缩状态为k,i行的压缩状态为j，然后用滚动数组优化了一下，注意如果不预处理不可存放位置会超时

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N (1<<8)
 4 #define FFC(i,a,b) for(int i=a;i<=b;++i)
 5     
 6 int T,n,dp[2][23][N][N],g[N],num[N],f1[N][N],f2[N][N],cur,ans;
 7 
 8 void init(){//预处理不可放的位置，和每一个压缩状态的骑士数目
 9     FFC(i,0,N-1){
10         FFC(j,0,7)if(i&(1<<j))num[i]++;
11         FFC(j,0,N-1){
12             if(((i>>2)&j)||((j>>2)&i))f1[i][j]=1;
13             if(((i>>1)&j)||((j>>1)&i))f2[i][j]=1;
14         }
15     }
16 }
17 int fuck(){
18     memset(dp,0,sizeof(dp));
19     cur=0,ans=0,dp[0][0][0][0]=1;
20     FFC(i,0,7){
21         FFC(j,0,n)FFC(p,0,N-1)FFC(q,0,N-1){
22             if (dp[cur][j][p][q]==0)continue;
23             FFC(z,0,N-1)
24                 if (((z&g[i+1])!=z)||num[z]+j>n||(i>=1&&f1[q][z])||(i>=2&&f2[p][z]))continue;
25                 else dp[cur^1][num[z]+j][q][z]+=dp[cur][j][p][q];
26         }
27         memset(dp[cur],0,sizeof(dp[cur])),cur^=1;
28     }
29     FFC(i,0,N-1)FFC(j,0,N-1)ans+=dp[cur][n][i][j];
30     return ans;
31 }
32 
33 int main() {
34     init();char str[N];
35     scanf("%d",&T);
36     while (T--){
37         scanf("%d",&n);    
38         memset(g,0,sizeof(g));
39         FFC(i,1,8){
40             scanf("%s",str);
41             FFC(j,0,7){
42                 g[i]<<=1;
43                 if(str[j]=='.')g[i]|=1;
44             }
45         }
46         printf("%d
",fuck());
47     }
48     return 0;
49 }

View Code