题意
给定长度为 $n$ 的数组 $c$，重排它，最大化最大子段和。
给出一些限制 $\left(a_i, b_i\right)$，表示原始数组中的第 $a_i$ 个元素必须在第 $b_i$ 个元素之前。
$n = 50$
题解
我们可以把数组分为三个部分：最大子段和所在区间的前面、最大子段和所在区间、最大子段和所在区间的后面。
注意到每个部分中的元素的位置顺序是无关紧要的。
于是现在问题变成了把每个数分到一个部分里，且原始数组中的第 $a_i$ 个元素所在部分必须不在第 $b_i$ 个元素所在部分之后。
于是可以网络流最小割解决。
- 若 $c_i > 0$，源点 $S$ 向每个 $i_1$ 连权值为 $c_i$ 的边，$i_1$ 向 $i_2$ 连权值为 $0$ 的边，$i_2$ 向 汇点 $T$ 连权值为 $c_i$ 的边。
- 若 $c_i < 0$，源点 $S$ 向每个 $i_1$ 连权值为 $0$ 的边，$i_1$ 向 $i_2$ 连权值为 $-c_i$ 的边，$i_2$ 向 汇点 $T$ 连权值为 $0$ 的边。
答案即为 $-MinCut + \sum\limits_ic_i$
对于一组限制 $\left(a_i, b_i\right)$：${a_i}_1$ 向 ${b_i}_1$ 连一条权值为 $\infty$ 的边，${a_i}_2$ 向 ${b_i}_2$ 连一条权值为 $\infty$ 的边。
代码
由于 TopCoder 最近无法提交，代码正确性未知。
struct RatingProgressAward {
int maximalProgress(vector<int> chg, vector<int> a, vector<int> b) {
tp sum = 0;
vector<vector<pair<tp, tp>>> e(2 * chg.size() + 3);
tp s = chg.size() * 2 + 1, t = s + 1;
for (tp i = 0; i < chg.size(); ++i) {
if (chg[i] == 0) continue;
if (chg[i] > 0) {
e[s].emplace_back(i, chg[i]);
e[i].emplace_back(i + chg.size(), 0);
e[i + chg.size()].emplace_back(t, chg[i]);
sum += chg[i];
} else {
e[s].emplace_back(i, 0);
e[i].emplace_back(i + chg.size(), -chg[i]);
e[i + chg.size()].emplace_back(t, 0);
}
}
for (tp i = 0; i < a.size(); ++i) {
e[a[i]].emplace_back(b[i], INF);
e[a[i] + chg.size()].emplace_back(b[i] + chg.size(), INF);
}
return sum - static_cast<int>(lib::Max_Flow(e, s, t));
}
};