题目传送门：LOJ #2146。
题意简述：
有 (n) 种寿司，第 (i) 种寿司的类型为 (a_i)。
如果你吃了第 (i) 种到第 (j) 种寿司，你会得到 (d_{i,j})（(ile j)）的收益。
如果你吃了 (c)（(c>0)）种类型为 (x) 的寿司，你会付出 (mx^2+cx) 的代价（(min{0,1})）。
最大化收益与代价的差。
题解：
一种经典的模型：最大权闭合子图。
模型：有若干个物品，每种物品有一个可正可负的价值 (v_i)，选取了物品就意味着获得了价值。
物品之间有限制关系：(x o y) 表示若要选择物品 (x) 则必须选择物品 (y)。
目标是最大化价值和。
显然，有时需要为了一个拥有较大价值的物品而被迫选择负价值的物品。
考虑使用最小割解决此类问题：
将每个物品与源 (S) 汇 (T) 相连。若割掉与 (S) 相连的边表示不选这个物品，割掉与 (T) 相连的边表示选择这个物品。
对于一个物品的价值 (v)，如果 (v>0) 则令它与 (S) 相连的边的权值为 (v)，与 (T) 相连的边的权值为 (0)，将 (v) 加入答案。表示不选择这个物品会付出 (v) 的代价；
如果 (v<0) 则令它与 (S) 相连的边的权值为 (0)，与 (T) 相连的边的权值为 (-v)（显然 (-v>0)）。表示选择这个物品会付出 (-v) 的代价。
对于 (x o y) 的关系，转化为 (x) 向 (y) 连一条权值为 (infty) 的边，显然这条边永远不会被割，如果选择了 (x)，即割掉 (x) 与 (T) 相连的边，那么如果不选 (y)，即割掉 (y) 与 (S) 相连的边，就会出现路径 (S o x o y o T)，所以必须选择 (y)。而如果不选 (x) 则对 (y) 的选择没有影响。
因为权值全部为非负数，符合使用 Dinic 算法解决网络流的条件，结合最大流最小割定理，可以使用 Dinic 算法解决此类问题。
回到题目上来，我们将每种 (d_{i,j}) 的收益都看做一个物品。显然如果选择 (d_{i,j})（(i<j)），则必须选择 (d_{i,j-1}) 以及 (d_{i+1,j})。
而如果吃了 (c)（(c>0)）种类型为 (x) 的寿司，需要付出 (mx^2+cx) 的代价。
这可以转化为：吃了每种类型为 (x) 的寿司需要付出 (x) 的代价，而吃过类型为 (x) 的寿司需要付出 (mx^2) 的代价。
选择了 (d_{i,i}) 就代表吃掉了第 (i) 种寿司，这时需要付出 (a_i) 的代价（(a_i) 是这种寿司的类型）。
选择了 (d_{i,i}) 还意味着：必须付出 (mcdot a_i^2) 的代价，我们将每个寿司类型也看作一个物品，选择收益 (d_{i,i}) 则必须选择类型 (a_i)。
至此，所有限制都转化为了“选择 (x) 则必须选择 (y)”的形式，可以使用最大权闭合子图的模型解决了。
在代码中，(S)、(T) 分别是 (1) 和 (2) 号点，(d_{i,j}) 是 (mathrm{Id}[i][j]) 号点，接下来的点则是每种寿司类型。
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const LL Inf = 0x7fffffffffffffff;
namespace DinicFlow {
const int MN = 6060, MM = 16055;
int N, S, T;
int h[MN], iter[MN], nxt[MM * 2], to[MM * 2], tot = 1; LL w[MM * 2];
inline void ins(int u, int v, LL x) { nxt[++tot] = h[u], to[tot] = v, w[tot] = x, h[u] = tot; }
inline void insw(int u, int v, LL x) { ins(u, v, x); ins(v, u, 0); }
int lv[MN], que[MN], l, r;
inline bool Lvl() {
memset(lv, 0, sizeof(lv));
lv[S] = 1;
que[l = r = 1] = S;
while (l <= r) {
int u = que[l++];
for (int i = h[u]; i; i = nxt[i]) if (w[i] && !lv[to[i]]) {
lv[to[i]] = lv[u] + 1;
que[++r] = to[i];
}
}
return lv[T] != 0;
}
LL Flow(int u, LL f) {
if (u == T) return f;
LL d = 0, s = 0;
for (int &i = iter[u]; i; i = nxt[i]) if (w[i] && lv[to[i]] == lv[u] + 1) {
d = Flow(to[i], std::min(f, w[i]));
f -= d, s += d;
w[i] -= d, w[i ^ 1] += d;
if (!f) break;
}
return s;
}
inline LL Dinic() {
LL Ans = 0;
while (Lvl()) {
memcpy(iter + 1, h + 1, N * sizeof(h[0]));
Ans += Flow(S, Inf);
}
return Ans;
}
}
const int MN = 105;
int N, M, A[MN], MxA;
int F[MN][MN], Id[MN][MN], cnt;
LL Ans = 0;
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), MxA = std::max(MxA, A[i]);
DinicFlow::S = 1, DinicFlow::T = 2;
cnt = 2;
for (int i = 1; i <= N; ++i) for (int j = i; j <= N; ++j) {
scanf("%d", &F[i][j]), Id[i][j] = ++cnt;
}
for (int i = 1; i <= N; ++i) for (int j = i; j <= N; ++j) {
int cost = F[i][j];
if (i == j) {
if (M) DinicFlow::insw(Id[i][j], cnt + A[i], Inf);
cost -= A[i];
}
else {
DinicFlow::insw(Id[i][j], Id[i + 1][j], Inf);
DinicFlow::insw(Id[i][j], Id[i][j - 1], Inf);
}
if (cost > 0) DinicFlow::insw(1, Id[i][j], cost), Ans += cost;
if (cost < 0) DinicFlow::insw(Id[i][j], 2, -cost);
}
if (M) for (int i = 1; i <= MxA; ++i) DinicFlow::insw(++cnt, 2, i * i);
DinicFlow::N = cnt;
printf("%lld
", Ans - DinicFlow::Dinic());
return 0;
}