P1896 [scoi2005] non aggression
Weihe 2021-06-27 15:00:07

Title Description

stay N×N In my chessboard K A king , So that they don't know each other ***, How many layout plans are there . The king can *** Up, down, left and right , And a grid in the upper left, lower left, upper right and lower right directions , common 8 Lattice .

notes : The data has been strengthened (2018/4/25)

I / O format

Input format :

There is only one line , It contains two numbers N,K ( 1 <=N <=9, 0 <= K <= N * N)

Output format :

The number of schemes obtained

I/o sample

sample input #1: 
3 2
sample output #1: 
16

 

Solution:

This topic is about dp Water problem .

Preprocess the legal status and the number of Kings placed in a single line , Definition $f[i][j][k]$ Before presentation $i$ OK, let it go $j$ And the last line is $k$ When the number of programs .

So the transfer is simpler , One layer enumeration phase j( The number of Kings ), The second level enumeration phase i( Row number ), The third layer enumerates States k( The last line is king state ), The fourth level enumerates decisions p( Post transition state ), It's just a matter of judging if it's legal .

Code :

/*Code by 520 -- 10.14*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=10;
int n,m,lim,w[1<<N];
ll f[N][N*N*2][1<<N],ans;
bool sta[1<<N];
int main(){
ios::sync_with_stdio(0);
cin>>n>>m,lim=(1<<n)-1;
For(i,0,lim) {
sta[i]=(!(i&(i<<1))&&!(i&(i>>1)));
if(sta[i])
For(j,0,n-1) if(i&(1<<j)) w[i]++;
}
f[0][0][0]=1;
For(p,0,m) For(i,1,n) For(j,0,lim)
if(sta[j]) For(k,0,lim)
if(sta[k]&&!(j&k)&&!((j<<1)&k)&&!((j>>1)&k))
f[i][p+w[j]][j]+=f[i-1][p][k];
For(i,0,lim) ans+=f[n][m][i];
cout<<ans;
return 0;
}

 

 
 
 
Please bring the original link to reprint ,thank
Similar articles

2021-06-15