P1896 [scoi2005] non aggression (shape pressure DP)

[SCOI2005] Don't invade each other - Luogu https://www.luogu.com.cn/problem/P1896 Elementary pressure dp, I learned a lot after reading the first solution , First of all, the compression of a matrix can start with rows , Record the status in the current line , First, let's look at this topic and think about 3 Status , Place of action , Current row status and number of Kings . So we need to think about the recurrence equation as f[i][j][k](i For the current line ,j In this line ,k For the number of Kings )+=f[i-1][s][k-t](s Is the status of the previous line ,t For the number of kings in this line )

So we have to deal with the possible states in a line and the number of kings in the changed state in advance , So the second dimension can be optimized as the number of this state , This also solves the number of kings in a row ,（ I really learned a lot after reading the solution , Before, I foolishly thought that I would put the state directly on the second dimension of the array , It's easy to explode ,orz bosses ）

Then we have to judge the transfer conditions

s&j when It means that up and down can attack

s<<1&j Attack from the bottom left to the top right

j<<1&s Attack from top left to bottom right

Then you can be happy code 了

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;

int sit[2000], gs[2000];
int cnt = 0;
int n, yong;
ll f[10][2000][100];
void dfs(int he, int sum, int node) {
	if (node >= n) {
		sit[++cnt] = he;
		gs[cnt] = sum;
		return;
	}
	dfs(he, sum, node + 1);
	dfs(he + (1 << node), sum + 1, node + 2);
}

int main() {
	scanf("%d %d", &n, &yong);
	dfs(0, 0, 0);
	for (int i = 1; i <= cnt; i++)
		f[1][i][gs[i]] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= cnt; j++) {
			for (int k = 1; k <= cnt; k++) {
				if (sit[j]&sit[k])
					continue;
				if ((sit[j] << 1)&sit[k])
					continue;
				if (sit[j] & (sit[k] << 1))
					continue;
				for (int s = yong; s >= gs[j]; s--)
					f[i][j][s] += f[i - 1][k][s - gs[j]];
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= cnt; i++) {
		ans += f[n][i][yong];
	}
	printf("%lld\n", ans);
	return 0;
}