題目描述：

P3749 [六省聯考 2017] 壽司餐廳

題目描述

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$ 的壽司，則她需要為這些壽司付出 $m{x}^2+cx$ 元錢，其中 $m$ 是餐廳給出的一個常數。

現在 Kiana 想知道，在這家餐廳吃壽司，自己能獲得的總美味度（包括所有吃掉的單種壽司的美味度和所有被累加的綜合美味度）減去花費的總錢數的最大值是多少。由于她不會算，所以希望由你告訴她。

輸入格式

第一行包含兩個正整數 $n,m$，分別表示這家餐廳提供的壽司總數和計算壽司價格中使用的常數。
第二行包含 $n$ 個正整數，其中第 $k$ 個數 $a_k$ 表示第 $k$ 份壽司的代號。
接下來 $n$ 行，第 $i$ 行包含 $n?i+1$ 個整數，其中第 $j$ 個數 $d_{i,i+j?1}$ 表示吃掉壽司能獲得的相應的美味度，具體含義見問題描述。

輸出格式

輸出共一行包含一個正整數，表示 Kiana 能獲得的總美味度減去花費的總錢數的最大值。

輸入輸出樣例 #1

輸入 #1

3 1
2 3 2
5 -10 15
-10 15
15

輸出 #1

12

輸入輸出樣例 #2

輸入 #2

5 0
1 4 1 3 4
50 99 8 -39 30
68 27 -75 -32
70 24 72
-10 81
-95

輸出 #2

381

輸入輸出樣例 #3

輸入 #3

10 1
5 5 4 4 1 2 5 1 5 3
83 91 72 29 22 -5 57 -14 -36 -3
-11 34 45 96 32 73 -1 0 29
-48 68 44 -5 96 66 17 74
88 47 69 -9 2 25 -49
86 -9 -77 62 -10 -30
2 40 95 -74 46
49 -52 2 -51
-55 50 -44
72 22
-68

輸出 #3

1223

說明/提示

樣例解釋 1

在這組樣例中，餐廳一共提供了 $3$ 份壽司，它們的代號依次為 $a_1=2,a_2=3,a_3=2$，計算價格時的常數 $m=1$。

在保證每次取壽司都能獲得新的美味度的前提下，Kiana 一共有 $14$ 種不同的吃壽司方案。以下列出其中幾種：

1. Kiana 一個壽司也不吃，這樣她獲得的總美味度和花費的總錢數都是 $0$，兩者相減也是 $0$；
2. Kiana 只取 $1$ 次壽司，且只取第 $1$ 個壽司，即她取壽司的情況為 $\{[1,1]\}$，這樣獲得的總美味度為 $5$，花費的總錢數為 $1\times 2^2+1\times 2=6$，兩者相減為 $?1$；
3. Kiana 取 $2$ 次壽司，第一次取第 $1,2$ 個壽司，第二次取第 $2,3$ 個壽司，即她取壽司的情況為 $\{[1,2],[2,3]\}$，這樣獲得的總美味度為 $5+(?10)+15+(?10)+15=15$，花費的總錢數為 $(1\times 2^2+2\times 2)+(1\times 3^2+1\times 3)=20$，兩者相減為 $?5$；
4. Kiana 取 $2$ 次壽司，第一次取第 $1$ 個壽司，第二次取第 $3$ 個壽司，即她取壽司的情況為 $\{[1,1],[3,3]\}$，這樣獲得的總美味度為 $5+15=20$，花費的總錢數為 $1\times 2^2+2\times 2=8$，兩者相減為 $12$。

在 $14$ 種方案中，惟一的最優方案是列出的最后一種方案，這時她獲得的總美味度減去花費的總錢數的值最大為 $12$。

數據范圍

對于所有數據，保證 $?500\le d_{i,j}\le 500$。

數據的一些特殊約定如下表：

Case #	$n$	$a_i$	$m$	附加限制
1	$\le 2$	$\le 30$	$=0$	-
2	$\le 2$	$\le 30$	$=1$	-
3	$\le 3$	$\le 30$	$=0$	-
4	$\le 3$	$\le 30$	$=1$	-
5	$\le 5$	$\le 30$	$=0$	-
6	$\le 5$	$\le 30$	$=1$	-
7	$\le 10$	$\le 30$	$=0$	所有的 $a_i$ 相同
8	$\le 10$	$\le 30$	$=1$	-
9	$\le 15$	$\le 30$	$=0$	所有的 $a_i$ 相同
10	$\le 15$	$\le 30$	$=1$	-
11	$\le 30$	$\le 1000$	$=0$	所有的 $a_i$ 相同
12	$\le 30$	$\le 30$	$=0$	所有的 $a_i$ 相同
13	$\le 30$	$\le 1000$	$=0$	-
14	$\le 30$	$\le 1000$	$=1$	-
15	$\le 50$	$\le 1000$	$=0$	所有的 $a_i$ 相同
16	$\le 50$	$\le 30$	$=0$	所有的 $a_i$ 相同
17	$\le 50$	$\le 1000$	$=0$	-
18	$\le 50$	$\le 1000$	$=1$	-
19	$\le 100$	$\le 1000$	$=0$	-
20	$\le 100$	$\le 1000$	$=1$	-

---

在讀題的過程中，我們不難發現題目中的幾個量之間存在依賴關系，且這些依賴關系構成了一張最大權閉合子圖，再結合題目給的數據范圍，我們不難想到這道題可以利用網絡流去解決。

最大權閉合子圖在網絡流中是一個常見的模型：
有若干個物品，每種物品有一個可正可負的價值 $v$ ，選取了物品就意味著獲得了價值。
物品之間有限制關系：$x\to y$ 表示若要選擇物品 $x$ 則必須選擇物品 $y$
對于這類問題，我們考慮用最小割去解決：
我們有源點s，匯點t。 源點向每個點都建邊，每個點都向匯點建邊。若割掉源點的邊則認為不選當前點，若割掉當前點向匯點的連邊則認為選擇當前點。
那么具體連邊要怎么連呢？
如果當前點的價值v為正數，那么讓答案加上當前點的價值，并且讓當前點和源點連容量為v的邊
如果當前點的價值v為負數，那么讓當前點和匯點連容量為-v的邊。
最小割就是在這個最大權閉合子圖上的最大流。

那么答案就是$ans?maxflow$

好，那么回歸這個題。
我們將每一個$d_{i,j}$都看做一個點，價值就是他本身的值。
且這些點根點之間都有依賴關系：若想選$d_{i,j}$，就必須選$d_{i,j?1}$和$d_{i+1,j}$
只需要讓當前點向這兩個點連容量為正無窮的邊即可。
同時這個題還有一個壽司種類的限制，想要處理這個限制，最好的辦法就是把壽司種類也加入這個圖中，且他的價值為$?m?a[i]?a[i]$
他跟$d_{i,i}$存在限制：$d_{i,i}?>a[i]$
且我們沒選一個壽司就要扣除他種類編號的價值，也就是令$d_{i,i}$的價值再減去$a[i]$
在這張圖上跑最大流即可求出答案。

---

#include<bits/stdc++.h>
using namespace std;const int N = 1e4+100,inf = 1e9+100;
struct Node{int y,Next,v;
}e[100*N];
int len = 1,Linkk[N];
int n,m;
int a[N],d[1000][1000];
int id[1000][1000],idx[10*N];
int ans = 0,cnt = 0;
int st,ed;
map < int , int > M;void Insert(int x,int y,int v){e[++len] = (Node){y,Linkk[x],v};Linkk[x] = len;e[++len] = (Node){x,Linkk[y],0};Linkk[y] = len;
}int de[N];bool bfs(){queue < int > q;for (int i = 1; i <= n; i++) de[i] = 0;de[st] = 1; q.push(st);while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y;if (de[y] || e[i].v == 0) continue;de[y] = de[x]+1;if (y == ed) return 1;q.push(y);}}return 0;
}int dinic(int x,int re){if (x == ed) return re;int now = re;for (int i = Linkk[x]; i && re; i = e[i].Next){int y = e[i].y;if (e[i].v == 0 || de[y] != de[x]+1) continue;int k = dinic(y,min(e[i].v,re));if (k == 0) de[y] = 0;re-=k;e[i].v-=k; e[i^1].v+=k;}return now-re;
}void Work(){len = 1;cin>>n>>m;st = ++cnt; ed = ++cnt;for (int i = 1; i <= n; i++){cin>>a[i];if (!M[a[i]]) M[a[i]] = 1 , idx[a[i]] = ++cnt;}M.clear();for (int i = 1; i <= n; i++){if (M[a[i]]) continue;M[a[i]] = 1;if (m) Insert(idx[a[i]],ed,m*a[i]*a[i]);}for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++){cin>>d[i][j],id[i][j] = ++cnt;int v = d[i][j];if (i == j){v = v-a[i];if (m) Insert(id[i][j],idx[a[i]],inf);}if (v > 0){ans+=v;Insert(st,id[i][j],v);}else Insert(id[i][j],ed,-v);}for (int i = 1; i <= n; i++)for (int j = i+1; j <= n; j++){int x = id[i][j] ,y ;if (i + 1 <= n) y = id[i+1][j],Insert(x,y,inf);y = id[i][j-1]; Insert(x,y,inf);}int maxf = 0;n = cnt;while (bfs()) maxf+=dinic(st,inf);cout<<ans-maxf<<endl;return; 
}int main(){ios::sync_with_stdio(false);cin.tie(0);int _ = 1; while (_--) Work();return 0;
}