Luogu P1896 non aggression (shape pressure dp)

Title Description

In \ × Put \ (K \) kings on the chessboard of N \) so that they don't attack each other. How many placement schemes are there in total. The king can attack one grid in its upper, lower, left, lower, left, lower, right, upper and lower eight directions, a total of \ (8 \) grids.

Input format

There is only one line containing two numbers \ (N, K \) \ ((1 < = N < = 9, 0 < = k < = N * N) \)

Output format

Number of schemes obtained

Sample input and output

Enter #1
3 2
Output #
16

thinking

In fact, at first I thought it was a search question, because it really looked like it.

But this is a pressure dp. However, I am not very clear about what is pressure dp. It should be to compress a state into a binary number, so as to reduce the space complexity. So how does this problem convert the state into binary number? In fact, it's not difficult. It's even obvious that we can use a binary number to represent the placement of kings in a row. For example, the number \ (1010101 \) means that there are kings in the \ (1,3,5,7 \) column. On the contrary, there are no kings in the \ (2,4,6 \) column. If the state is designed, how to transfer the state?

First of all, we need to judge whether this number can be placed in a row alone, which can be solved by preprocessing. Secondly, we should judge whether the placement of the next line will conflict with that of the current line. In fact, the code implementation is very simple. We only need to move the binary number of the next line to the left and right by one bit respectively, and then compare it. Because a king occupies the surrounding eight grids, there can be no king in the left column and the right column. In binary numbers, there can only be one \ (1 \) in adjacent bits. One bit to the left, one bit to the right, plus itself. Then perform the one digit operation of \ (& \) with the current line. It is not difficult to think that if the conditions are met, the results obtained after the operation should be \ (0 \). The transfer conditions are also solved.

Finally, the initialization and state transition equations are considered. A three-dimensional array f[i][j][k] can be used to indicate that the state of line I is j (after being converted to binary, it indicates the state), and K kings have been placed. Then the state transition equation is f[i][j][k+tot(j)]+=f[i-1][s][k], where the tot function is used to calculate the number of \ (1 \) in the binary state, that is, the number of kings in the current line, and \ (s \) represents the qualified state in the previous line, which can be enumerated. Initialization only needs the first line. As long as the king is less than the given \ (K \) (it seems that the variable name is repeated), the number of schemes will be changed to \ (1 \). Then I cut the blue question.

Don't open longlong to see your ancestors

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
int n,k,cnt,b[2000];
long long ans,f[10][2000][100];
int tot(int x){
	int sum=0;
	while(x){
		if(x&1){
			sum++;
		}
		x>>=1;
	}
	return sum;
}//Count the number of 1
int main()
{
	scanf("%d%d",&n,&k);
	int p=pow(2,n)-1;
	for(int i=0;i<=p;i++){
//		printf("%d %d\n",i>>1,i<<1);
		int r=i&(i>>1),t=i&(i<<1);
//		printf("%d %d\n",r,t);
		if((r==0)&&(t==0)){
			b[++cnt]=i;
//	    	printf("%d\n",i);
		}
	}//Preprocessing: first preprocess the qualified conditions of each line, so that the cycle can directly meet the conditions without recycling redundancy 
	for(int i=1;i<=cnt;i++){
		if(tot(b[i])<=k){//Cannot exceed k 
			f[1][b[i]][tot(b[i])]=1;//No matter how the first line is placed, there will be no repetition, so the number of schemes is 1 
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=cnt;j++){
			for(int p=1;p<=cnt;p++){
				if(b[j]&b[p]) continue;
				if(b[j]&(b[p]<<1)) continue;
				if(b[j]&(b[p]>>1)) continue;//Judge whether the current line and the previous line are legal
				for(int s=1;s<=k;s++){
					if(tot(b[j])+s<=k){
						f[i][b[j]][tot(b[j])+s]+=f[i-1][b[p]][s];//If there are no more kings, the number of schemes will be accumulated
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt;j++){
			ans+=f[i][b[j]][k];//Because there are not necessarily enough k in which line and state, then accumulate the answers
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Tags: Dynamic Programming

Posted by dbomb101 on Mon, 23 May 2022 11:30:05 +0300