题目描述：
Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。
每天晚上，这家餐厅都会按顺序提供 \(n\) 种寿司，第 \(i\) 种寿司有一个代号 \(a_i\) 和美味度 \(d_{i, i}\)，不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的，Kiana 也可以无限次取寿司来吃，但每种寿司每次只能取一份，且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段，即 Kiana 可以一次取走第 \(1, 2\) 种寿司各一份，也可以一次取走第 \(2, 3\) 种寿司各一份，但不可以一次取走第 \(1, 3\) 种寿司。
由于餐厅提供的寿司种类繁多，而不同种类的寿司之间相互会有影响：三文鱼寿司和鱿鱼寿司一起吃或许会很棒，但和水果寿司一起吃就可能会肚子痛。因此，Kiana 定义了一个综合美味度 \(d_{i, j} \ (i < j)\)，表示在一次取的寿司中，如果包含了餐厅提供的从第 \(i\) 份到第 \(j\) 份的所有寿司，吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间，所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时，不止一个综合美味度会被累加，比如若 Kiana 一次取走了第 \(1, 2, 3\) 种寿司各一份，除了 \(d_{1, 3}\) 以外，\(d_{1, 2}, d_{2, 3}\) 也会被累加进总美味度中。
神奇的是，Kiana 的美食评判标准是有记忆性的，无论是单种寿司的美味度，还是多种寿司组合起来的综合美味度，在计入 Kiana 的总美味度时都只会被累加一次。比如，若 Kiana 某一次取走了第 \(1, 2\) 种寿司各一份，另一次取走了第 \(2, 3\) 种寿司各一份，那么这两次取寿司的总美味度为 \(d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3}\)，其中 \(d_{2, 2}\) 只会计算一次。
奇怪的是，这家寿司餐厅的收费标准很不同寻常。具体来说，如果 Kiana 一共吃过了 \(c \ (c > 0)\) 种代号为 \(x\) 的寿司，则她需要为这些寿司付出 \(mx^2 + cx\) 元钱，其中 \(m\) 是餐厅给出的一个常数。
现在 Kiana 想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她不会算，所以希望由你告诉她。
对于所有数据，保证 \(-500 \leq d_{i, j} \leq 500,n \le 100,a_i \le 1000,m \in \{0,1\}\)。
题目分析：
看到这个 \(d_{i,j}\) 就很有支配的味道，也就是如果要有 \(d_{i,j}\) 的贡献，则必定会有 \(d_{i+1,j}\) 和 \(d_{i,j-1}\) 的贡献。
其实就是一个选 X 则必须选 Y 的形式，也就是最大权闭合子图问题，这个看上去就很有前途，所以考虑怎么扩展到解决 \(mx^2 + cx\) 的代价，也就是怎么转化为选 X 则必选 Y 的形式。
对于 \(cx\) 的代价可以理解为每次选择类型为 \(x\) 的物品需要 \(x\) 的代价，也就是我们选择 \(d_{i,i}\) 就意味着要付出 \(a_i\) 的代价。
而对于 \(mx^2\) 的代价，因为也是只会产生一次贡献，所以我们可以考虑对于每一个类型建一个点，然后就是意味着选 \(d_{i,i}\) 必须选 \(a_i\)。
最后直接跑一下最大权闭合子图的模板就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int INF = 1e16+5;
struct edge{
int nxt,to,val;
edge(){}
edge(int _nxt,int _to,int _val){
nxt = _nxt,to = _to,val = _val;
}
}e[N];
int n,m,s,t,cnt = 1,head[N],cur[N],dep[N],tot,a[N],num[1005][1005],f[1005][1005];
bool vis[N];
void add_edge(int from,int to,int val){
e[++cnt] = edge(head[from],to,val);
head[from] = cnt;
e[++cnt] = edge(head[to],from,0);
head[to] = cnt;
}
bool bfs(){
memset(vis,false,sizeof(vis));memset(dep,0,sizeof(dep));memcpy(cur,head,sizeof(head));
dep[s] = 1;
queue<int> q;q.push(s);
while(!q.empty()){
int now = q.front();q.pop();
if(vis[now]) continue;
vis[now] = true;
for(int i = head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(e[i].val && !dep[to]){
dep[to] = dep[now] + 1;
q.push(to);
}
}
}
return dep[t] != 0;
}
int dfs(int now,int limit){
if(now == t) return limit;
int flow = 0;
for(int i = cur[now]; flow < limit && i; i = e[i].nxt){
cur[now] = i;
int to = e[i].to;
if(dep[to] == dep[now] + 1 && e[i].val){
int h = dfs(to,min(limit - flow,e[i].val));
e[i].val -= h;e[i^1].val += h;flow += h;
if(!h) dep[to] = INF;
}
}
return flow;
}
int dinic(){
int ans = 0,flow;
while(bfs()){
while(flow = dfs(s,INF)){
ans += flow;
}
}
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
s = 1,t = 2;tot = 2;
int mx = 0;
for(int i=1; i<=n; i++) scanf("%lld",&a[i]),mx = max(mx,a[i]);
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
scanf("%lld",&f[i][j]);
num[i][j] = ++tot;
}
}
int tmp = 0;
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
int cst = f[i][j];
if(i == j){
if(m) add_edge(num[i][j],tot + a[i],INF);
cst -= a[i];
}
else{
add_edge(num[i][j],num[i+1][j],INF);
add_edge(num[i][j],num[i][j-1],INF);
}
if(cst > 0) add_edge(1,num[i][j],cst),tmp += cst;
if(cst < 0) add_edge(num[i][j],2,-cst);
}
}
if(m) for(int i=1; i<=mx; i++) add_edge(++tot,2,i * i);
printf("%lld\n",tmp - dinic());
return 0;
}