1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1202 Solved: 697
[ 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
我大四川05年的省选题,高二的时候做过,当时折腾得啊……虽然今天也被虐得不轻,但是比那时确实有进步!!
做过的题再做的一大弊端就是思路什么的已经早就知道了
状压dp
f【i】【j】【k】 表示第i行的状态为k 且已经放了j个国王的方案数
转移方程应该为
f[i][j][k] += f[i - 1][j - num[k]][p] (num[k]表示k状态的国王数)
再次提醒边界——注意要保证j - num[k]>0 不然就访问无效内存了,可能就会出现意想不到的后果哦
还有,事实证明要爆long 所以记得用longlong!!
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long n, k, m;
long state[600][2];
long long f[20][100][600];
long cala(long x)
{
long sum = 0;
while (x > 0)
{
if ((x & 1) == 1) sum++;
x >>= 1;
}
return sum;
}
int main()
{
//freopen("king.in", "r", stdin);
scanf("%d%d", &n, &k);
m = 0;
long r = ((1 << n) - 1);
for (long i = 0; i <= r; i++)
{
if ((i & (i >> 1)) == 0)
{
long tmp = cala(i);
if (tmp <= k)
{
m++;
state[m][0] = i;
state[m][1] = tmp;
}
}
}
memset(f, 0, sizeof(f));
for (long i = 1; i <= m; i++)
{
f[1][state[i][1]][i] = 1;
}
for (long i = 2; i <= n; i++)
{
for (long j = 0; j <= k; j++)
{
for (long p = 1 ; p <= m; p++)
for (long q = 1 ; q <= m; q++)
{
if ((state[p][0] & state[q][0]) != 0) continue;
if ((state[p][0] & (state[q][0] << 1)) != 0) continue;
if ((state[p][0] & (state[q][0] >> 1)) != 0) continue;
if ((j - state[q][1]) >= 0)
{
f[i][j][q] += f[i - 1][j - state[q][1]][p];
//cout << i<<' ' <<j <<' '<<q <<' '<< f[i][j][q]<< endl;
}
}
}
}
long long re = 0;
for (long i = 0; i <= m; i++)
{
re += f[n][k][i];
}
cout << re << endl;
return 0;
}