# BZOJ1087: [SCOI2005] mutual noninvasive King (DP)

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 5168  Solved: 3006
[Submit][Status][Discuss]

## Description

Put K kings in the N × N chessboard so that they don't attack each other. How many kinds of placement schemes are there. The king can attack it up and down, left and right, and up and left
There are 8 squares near each of the eight directions from left to right.

## Input

Only one line, including two numbers N, K (1 < = N < = 9, 0 < = k < = N * N)

## Output

Number of options.

3 2

16

## Source

\$f[i][j][k] \$indicates the first \$I \$line, the status of the \$I \$line is \$j \$, and \$k \$schemes are put

Enumerate the status of the previous line when transferring

Need to preprocess the number of kings in each state

```// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#define int long long
using namespace std;
const int MAXN = 10;
char buf[1<<22],*p1=buf,*p2=buf;
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int f[MAXN][1<<MAXN][MAXN*MAXN];
int N, K;
int times[1<<MAXN],can[1<<MAXN];
int calc(int x) {
int num = 0;
for(int i = 0;i < N; i++)
if( x & (1 << i) )
num++;
return num;
}
main() {
#ifdef WIN32
freopen("a.in","r",stdin);
#endif
//printf("%d %d %d\n",0<<1,0>>1,0);
int Max = (1 << N) - 1;
for(int i = 0;i < Max; i++)
times[i] = calc(i),
can[i] = (i & (i>>1)) == 0 ? 1 : 0;
f = 1;
for(int i = 1;i <= N; i++)
for(int j = 0;j < Max; j++)
if(can[j])
for(int k = 0;k < Max; k++)
if(((j & k) == 0) && ((j & (k << 1)) == 0) && ((j & (k >> 1)) == 0))
for(int l = times[j]; l <= K; l++)
f[i][j][l] += f[i-1][k][l - times[j]];
int ans = 0;
for(int i = 0;i <= Max; i++)
ans += f[N][i][K];
printf("%lld", ans);
return 0;
}```

Keywords: C++

Added by olivarespablo on Sun, 05 Apr 2020 14:10:51 +0300