BZOJ-1087 互不侵犯King 状压DP+DFS预处理

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.csdn.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;
}
上一篇:Spring Boot 2.x基础教程:使用JdbcTemplate访问MySQL数据库


下一篇:性能问题分析-CPU偏高