P1896 [SCOI2005] 互不侵犯(状压dp)

[SCOI2005] 互不侵犯 - 洛谷https://www.luogu.com.cn/problem/P1896初学状压dp，看了第一篇题解后的感觉学到了很多，首先矩阵的状压可以以行入手，记录在当前这一行的状态，首先我们看本题思考后有3个状态，所在行，当前行状态和国王数目。所以就要思考递推方程为f[i][j][k](i为当前行，j为此行状态，k为国王数目)+=f[i-1][s][k-t](s为上一行状态，t为这一行的国王数目)

所以我们要预先处理掉一行中可能的状态以及改状态下的国王数目，所以第二维可以优化为这一状态的编号，这样也同时解决了一行中的国王数目，（真的是看完那篇题解后学到了很多，之前还傻傻的以为就数组第二维直接放状态，这样很容易炸，orz大佬）

然后就要判断转移条件

s&j时 说明上下能攻击到

s<<1&j 左下右上攻击到

j<<1&s 左上右下攻击到

然后就可以愉悦的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;
}