题目链接：https://codeforces.com/contest/1420/problem/E
题目大意：
给你一个长度为 (n) 的 (01)序列，每一次操作你可以交换相邻的两个元素。
定义序列的 保护值（ protection ）为“序列中一对数值为 (0) 的数，且这对数之间夹着至少一个 (1)”的对数。
请计算当最多执行 (i) 次交换操作（(i in [0, frac{n(n-1)}{2}])）的情况下序列保护值的最大值各是多少。
问题分析
对于给定的一个 (01) 序列 (A)，我们定义另一种状态 (f(A)) 为 (A) 的另外一种表述方式。
(f(A)) 仍然是一个集合，但是它表示的含义如下：
- 其第一个元素表示 (A) 中第一个 (1) 前面的 (0) 的数量；
- 其第二个元素表示 (A) 中介于第一个 (1) 和第二个 (1) 之间的 (0) 的数量；
- ……
- 其最后一个元素表示在最后一个 (1) 后面的 (0) 的数量。
举个例子：(f(011000101100) = {1, 0, 3, 1, 0, 2})，在这个例子中：
- 在第一个 (1) 前面有 (1) 个 (0)；
- 在第一个 (1) 和第二个 (1) 之间有 (0) 个 (0)；
- 在第二个 (1) 和第三个 (1) 之间有 (3) 个 (0)；
- ……
- 在最后一个 (1) 后面有 (2) 个 (0)。
可以发现，将原始的 (A) 转换为 (f(A)) 并不困难。
现在，如果我们交换序列 (A) 中两个相邻的不同的数，(f(A)) 也会发生相应的变化。也就是说，一旦交换两个相邻的数，(f(A)) 中的一对相邻的数就会发生变化（一个加一，一个减一）。
让我们定义如下一个任务，定义两个序列 (A = { a_1, a_2, cdots, a_k }) 以及 (B = {b_1, b_2, cdots, b_k})。我们需要计算将序列 (A) 变成序列 (B) 的最少交换次数（明显地，(A)中所有元素之和等于(B)中所有元素之和）。
为了解决这个问题，我们假设在第(i)个元素后面设置一个“屏障”。于是序列(A)变成了两部分：左边部分（第(1)到(i)个元素）和右边部分（第(i+1)到(n)个元素）。为了让序列(A)和(B)的左右部分相同，你需要在第(i)和(i+1)个元素之间进行 (g_{A, B}(i) = left|sum_{j=1}^{i} a_i - sum_{j=1}^i b_i ight|) 次交换操作。而总的交换次数为
对于一个序列 (A) 来说，假设已知它的转换序列 (f(A) = {f_1, f_2, cdots, f_k})， 则我们可以通过如下公式求得序列的 保护值（ protection ）(p(A))：
因为 (sum_{i=1}^k f_i) 已知，所以我们的目的是最小化 (sum_{i=1}^k f_i^2) 。
我们定义 一轮交换 的含义是：第 (i) 轮我们交换了 (f_i) 和 (f_{i+1}) 若干次，然后最终的 (f_i) 确定下来了 —— 这样算一轮。（也就是第 (i) 轮交换，我们需要将 (f(A)) 中的第 (i) 个元素和第 (i+1) 个元素交换若干轮，交换结束时，第 (i) 个元素就确定了，这一轮交换才算完成）
接下来我们尝试找到序列 (f(A) = {f_1, f_2, cdots, f_k}) 在不超过 (k) 轮交换下的最佳序列。
我们需要定义一个状态 (dp_{i, s, k}) ，它表示的含义是：
我们已经确定了 (f(A)) 的前 (i) 个元素，并且进行了 (k) 轮 交换的情况下，并且 (sum_{i=1}^k f_i) 等于 (s) 的情况下，对应的 (sum_{i=1}^k f_i^2) 的最小值。
为了得到答案我们需要先计算得到 (dp_{i, c_0, k})，其中 (c_0) 表示原始序列中 (0) 的数量。
并且为了计算 (dp_{i, s, k}) 我们需要去遍历最终 (f_{i+1}) 可能的情况 —— 这里假设它会变为 (h)。
于是，可以得到状态转移方程如下：
这里， (z_i) 表示初始序列 (f(A)) 中 (sum_{j=1}^i f_i) 的值。
总体时间复杂度为 (O(n^5)) ，但是代码实现中常数比较小，所以最终的时间复杂度能达到 (O(frac{n^5}{27}))。
示例代码：
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 105;
int n, a[maxn], b[maxn], k, p[maxn], dp[maxn][maxn][maxn*(maxn-1)/2];
void chk_min(int &x, int y) {
x = min(x, y);
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
a[n] = 1;
for (int i = 0; i <= n; i ++) {
if (a[i] == 0) b[k] ++;
else k ++;
}
partial_sum(b, b+k, p);
memset(dp, 0x3f, sizeof(dp));
dp[0][0][0] = 0;
int l = p[k-1];
for (int i = 0; i < k; i ++) {
for (int j = 0; j <= l; j ++) {
for (int s = 0; s <= n*(n-1)/2; s ++) {
if (dp[i][j][s] == INF) continue;
for (int q = j; q <= l; q ++) {
chk_min(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j));
}
}
}
}
int mn = INF;
for (int s = 0; s <= n*(n-1)/2; s ++) {
chk_min(mn, dp[k][l][s]);
int val = l * l - mn;
assert(val % 2 == 0);
cout << val / 2 << " ";
}
return 0;
}