直接计算有多少对守卫被保护比较困难，可以计算有多少对守卫是没有被保护的。（只用考虑都没拿盾牌的就好了）
设有 \(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;
}