CF1420E

直接计算有多少对守卫被保护比较困难，可以计算有多少对守卫是没有被保护的。（只用考虑都没拿盾牌的就好了）

设有 \(t\) 个守卫拿着盾牌，初始状态为 \(a_{1\cdots n}\)。

这相当于在一个 \(01\) 串 \(s\) 中填写 \(t\) 个 \(1\)，将 \(s\) 中的 \(0\) 分成 \(t+1\) 个部分，设这些部分大小分别为 \(c_{1\cdots t+1}\)，那么就是要最小化 \(\sum \frac{c_i\times (c_i-1)}{2}\)。

定义一个 \(01\) 串 \(s\) 的代价为由 \(a\) 通过移动一个 \(1\) 到相邻的 \(0\) 的位置的操作变成 \(s\) 的最小操作次数。

显然 \(1\) 之间的相对位置是不会发生改变的。

因此设 \(a\) 中 \(1\) 的位置依次为 \(p_{1\cdots t}\)，\(s\) 中为 \(q_{1\cdots t}\)，则代价为 \(\sum \left|p_i-q_i\right|\)。

有了以上的铺垫，就可以 DP 了。

设 \(f(i,j,k,l)\) 为考虑到第 \(i\) 位，已经填了 \(j\) 个 \(1\)，并且最后一个 \(1\) 离 \(i\) 的距离是 \(k\)，代价为 \(l\) 的答案。

• 下一位不填 \(1\)。\(f(i+1,j,k+1,l)\gets f(i,j,k,l)+k\)。
• 下一位填 \(1\)。\(f(i+1,j+1,0,l+\left|p_{j+1}-(i+1)\right|)\gets f(i,j,k,l)\)。

设 \(g_i=\frac{(n-t)(n-t-1)}{2}-\min\limits_{k}f(n,t,k,i)\)，对 \(g_i\) 取个前缀 \(\max\) 即可。

时空复杂度均为 \(\mathcal O(n^5)\)，滚动数组优化一下空间是可以过的。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 85, M = 3205;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, a[N], pos[N], cnt;
bool vis[2][M][N][N];
ll f[2][M][N][N], ans[M];

void chkmin(int p, int j, int k, int l, ll v) {
	if (!vis[p][j][k][l]) f[p][j][k][l] = v, vis[p][j][k][l] = 1;
	else f[p][j][k][l] = min(f[p][j][k][l], v);
}

int main() {
	scanf("%d", &n), m = n * (n - 1) / 2;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		if (a[i]) pos[++cnt] = i;
	}
	if (cnt == n || !cnt) {
		for (int i = 0; i <= m; ++i) printf("%d ", 0);
		return 0;
	}
	vis[0][0][0][0] = 1;
	for (int i = 0, p = 0; i < n; ++i, p ^= 1)
		for (int j = 0; j <= m; ++j)
			for (int k = 0; k <= i; ++k)
				for (int l = 0; l <= i; ++l) if (vis[p][j][k][l]) {
					vis[p][j][k][l] = 0;
					chkmin(p ^ 1, j, k, l + 1, f[p][j][k][l] + l);
					if (k < cnt) chkmin(p ^ 1, j + abs(pos[k + 1] - (i + 1)), k + 1, 0, f[p][j][k][l]);
				}
	for (int i = 0; i <= m; ++i) {
		ans[i] = inf;
		for (int j = 0; j <= n; ++j) if (vis[n & 1][i][cnt][j]) ans[i] = min(ans[i], f[n & 1][i][cnt][j]);
		if (i) ans[i] = min(ans[i], ans[i - 1]);
	}
	for (int i = 0; i <= m; ++i) printf("%lld ", (n - cnt) * (n - cnt - 1) / 2 - ans[i]);
	return 0;
}

上述做法常数非常大。

不过可以简化一下状态定义，设 \(f(i,j,k)\) 表示考虑了前 \(i\) 位，第 \(i\) 位上填 \(1\)，已经填了 \(j\) 个 \(1\)，代价为 \(k\) 时候的答案。

转移就枚举下一个 \(1\) 填在哪，时间复杂度依旧为 \(\mathcal O(n^5)\)，但是空间复杂度降为了 \(\mathcal O(n^4)\)，该做法常数非常小。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 80, inf = 0x3f3f3f3f;
int n, a[N+5], cnt[2], pos[N+5];
int total, mx;
int f[N+5][N*(N-1)/2+5][N+5];

int calc(int x) {
	return x * (x - 1) / 2;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		++cnt[a[i]];
		if (a[i]) {
			pos[cnt[1]] = i;
		}
	}
	total = calc(cnt[0]);
	mx = calc(n);
	if (!cnt[1]) {
		for (int i = 0; i <= mx; ++i) printf("%d ", 0);
		return 0;
	}
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i < n; ++i) {
		f[i][abs(pos[1] - i)][1] = calc(i - 1);
		for (int j = 0; j <= mx; ++j) {
			for (int k = 1; k <= i && k < cnt[1]; ++k) if (f[i][j][k] != inf) {
				int rest = cnt[1] - k;
				for (int l = i + 1; l <= n - rest + 1; ++l) {
					int nxt = j + abs(pos[k + 1] - l);
					if (nxt <= mx) f[l][nxt][k + 1] = min(f[l][nxt][k + 1], f[i][j][k] + calc(l - i - 1));
				}
			}
		}
	}
	int ans = total;
	for (int j = 0; j <= mx; ++j) {
		for (int i = cnt[1]; i <= n; ++i) if (f[i][j][cnt[1]] != inf)
			ans = min(ans, f[i][j][cnt[1]] + calc(n - i));
		printf("%d ", total - ans);
	}
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16800284.html