1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2337 Solved: 1366
[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
16
刚学状压DP的蒟蒻A的第一道状压，一开始写的朴素状压，发现各种蛋疼根本就不对，（毕竟是个沙茶），于是搜了下题解（怪我啦），发现还是too young，too simple；高端的预处理让我膜拜，对于状压DP这方面现在是真的水的不行，还需要多多练习啊
此处传送门：http://blog.****.net/qpswwww/article/details/34516641
高端讲解！
傻×的程序附上：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int plan[1000]={0},map[1000][1000]={0},num[1000]={0};
long long f[10][100][1000]={0};
int n,k,zz=0;
void dfs(int king,int loc,int state)
{
plan[++zz]=state;
num[zz]=king;
if ((king>=(n+1)/2) || (king>=k)) return;
for (int i=loc+2; i<=n; i++)
dfs(king+1,i,state+(1<<(i-1)));
}
int main()
{
scanf("%d%d",&n,&k);
dfs(0,-1,0);
for (int i=1; i<=zz; i++)
for (int j=1; j<=zz; j++)
if ((plan[i] & plan[j]) || (plan[i]>>1 & plan[j]) || (plan[i]<<1 & plan[j]))
map[i][j]=map[j][i]=0;
else
map[i][j]=map[j][i]=1;
for (int i=1; i<=zz; i++)
f[1][num[i]][i]=1;
for (int i=2; i<=n; i++)
for (int j=0; j<=k; j++)
{
for (int t=1; t<=zz; t++)
{
if (num[t]>j) continue;
for (int l=1; l<=zz; l++)
if (map[l][t] && num[l]+num[t]<=j)
f[i][j][t]+=f[i-1][j-num[t]][l];
}
}
long long ans=0;
for (int i=1; i<=zz; i++)
ans+=f[n][k][i];
printf("%lld",ans);
return 0;
}