首页 > 代码库 > 【BZOJ 1087】 [SCOI2005]互不侵犯King
【BZOJ 1087】 [SCOI2005]互不侵犯King
1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1664 Solved: 984
[Submit][Status]
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数组中。
然后枚举a数组中所有两两组合的情况，判断是否可以成为相邻的两行（即满足上下不攻击的性质），用前向星存起来。
接下来就是状压dp了。
f[i][j][k]表示前i行用j个国王，第i行的国王放置情况为a[j]的方案数。
把i-1行与a[k]不冲突的方案数累加过来即可。
注意！！！这道题要用long long!!
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define LL long long
using namespace std;
struct edge
{
int y,ne;
}e[5005];
int cnt=0,tot=0,h[105],p[15],c[605],q[15],a[105],n,k;
LL f[15][105][105];
bool Ok(int x)
{
int s=x;
for (int i=1;i<=n;i++)
{
p[i]=x&1;
if (p[i]) c[s]++;
x>>=1;
}
for (int i=2;i<=n;i++)
{
if (p[i]&&p[i-1]) return false;
}
return true;
}
void Add(int x,int y)
{
tot++;
e[tot].y=y;
e[tot].ne=h[x];
h[x]=tot;
}
bool Can(int x,int y)
{
for (int i=1;i<=n;i++)
{
p[i]=x&1;
x>>=1;
}
for (int i=1;i<=n;i++)
{
q[i]=y&1;
y>>=1;
}
for (int i=1;i<=n;i++)
if (q[i]&&(p[i]||p[i-1]||p[i+1])) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&k);
if (k==0)
{
cout<<0<<endl;
return 0;
}
cnt=0;
for (int i=0;i<(1<<n);i++)
if (Ok(i))
a[++cnt]=i,f[1][c[i]][cnt]=1LL;
for (int i=1;i<=cnt;i++)
for (int j=1;j<=cnt;j++)
if (Can(a[i],a[j])) Add(i,j);
LL ans=0LL;
for (int i=2;i<=n;i++)
for (int now=1;now<=cnt;now++)
for (int u=c[a[now]];u<=k;u++)
for (int j=h[now];j;j=e[j].ne)
f[i][u][now]+=f[i-1][u-c[a[now]]][e[j].y];
for (int i=1;i<=cnt;i++)
ans+=f[n][k][i];
cout<<ans<<endl;
return 0;
}
【BZOJ 1087】 [SCOI2005]互不侵犯King
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。