【状态压缩DP】【BZOJ1087】【SCOI2005】互不侵犯king

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3135 Solved: 1825
[Submit][Status][Discuss]

Description

　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

　　只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

　　方案数。

Sample Input

3 2

Sample Output

Solution

　　本蒟蒻做的第一道状压DP，搞了一下午才A掉。

　　对于棋盘中每个位置都有两种状态——放和不放，我是用1来表示放国王，用0来表示不放国王，这样就可以用一个十进制数来表示每一行放国王的某一种方案。再看一眼数据，这么小直接枚举啊！！但这枚举也是有点讲究的。

　　首先我们枚举每一行所有放国王的可能的方案，我们发现如果某种方案不合法，那么（这种方案）&（这种方案>>1）一定不为零，这样就可以在枚举时排除不合法方案。接下来就是DP了。

　　说是DP，其实和枚举没差了。状态转移方程为：f[i+1][t+num[x]][x]+=f[i][t][y]，第一维表示第i行，第二维表示第i行及以上共放了几个国王，第三维表示第i行放国王的方案。也就是说，我们需要四重循环来花式枚举状态，枚举第 i 行，枚举当前行的方案，枚举下一行的方案，枚举放几个国王。DP完后将最后一行的所有位置的方案数相加即是正解。

　　最重要的一点：

　　不开long long见祖宗，十年OI一场空

　　下面是AC代码：

 1 #include <cstdio>
 2 int N,K,imp;
 3 int num[1010],jdg[1010];
 4 long long f[12][512][512];
 5 void enumeration(){
 6     for(int i=0;i<=imp;++i)
 7         if(!(i&(i<<1))){
 8             int temp=i;
 9             while(temp) {num[i]+=(temp&1); temp>>=1;}
10             jdg[i]=1; f[1][num[i]][i]=1;
11         }
12 }
13 long long int DP(){ //别被这缩进吓到了...
14     for(int i=1;i<N;++i)
15          for(int j=0;j<=imp;++j)
16             if(jdg[j])
17                 for(int k=0;k<=imp;++k)
18                     if(jdg[k])
19                         if((!(j&k))&&(!((j>>1)&k))&&(!((j<<1)&k)))
20                             for(int t=num[j];t+num[k]<=K;++t)
21                                 f[i+1][t+num[k]][k]+=f[i][t][j];
22     long long int ret=0;
23     for(int i=0;i<=imp;++i) ret+=f[N][K][i];
24     return ret;
25 }
26 int main(){
27     scanf("%d%d",&N,&K);
28     imp=(1<<N)-1; enumeration();
29     printf("%lld",DP());
30     return 0;
31 }