Description
Kiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上，这家餐厅都会按顺序提供n种寿司，第i种寿司有一个
代号ai和美味度di,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想知道，在这家餐厅吃寿司，自己能获得的总美
味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。由于她
不会算，所以希望由你告诉她
Input
第一行包含两个正整数n,m，分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。
第二行包含n个正整数，其中第k个数ak表示第k份寿司的代号。
接下来n行，第i行包含n-i+1个整数，其中第j个数d(i,i+j-1)表示吃掉寿司能
获得的相应的美味度，具体含义见问题描述。
N<=100,Ai<=1000
Output
输出共一行包含一个正整数，表示Kiana能获得的总美味度减去花费的总钱数的最大值。
Sample Input
3 1
2 3 2
5 -10 15
-10 15
15
Sample Output
12
题解
将区间看做点
每个[i,j]区间只要向[i+1,j],[i,j-1]连边
转换为最大权闭合子图
现在最麻烦的是解决每个点的权值
将单个的点即[i,j] (i==j)每个点的美味度减去它的代号(解决cm)向 Idx[a[i]]连边 Idx[]用来限制第一次吃的额外的花费
剩下的就和标准的最大权闭合子图一样了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int INF=0x7fffffff;
int idIndex;
int read(){
int res=0;
static char ch;int flag=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;
return res*flag;
}
struct edge{
int END,next,cap;
}v[1000005];
int first[10005],p;
void add(int a,int b,int c){
v[p].END=b;v[p].next=first[a];v[p].cap=c;first[a]=p++;
v[p].END=a;v[p].next=first[b];v[p].cap=0;first[b]=p++;
}
int a[150];
int Idx[1005],id[150][150];
int dis[10005],cur[10005];
bool vis[10005];
bool BFS(int S,int E){
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
vis[S]=1;dis[S]=0;
queue<int> Q;
Q.push(S);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=first[u];i!=-1;i=v[i].next){
if(!vis[v[i].END]&&v[i].cap>0){
vis[v[i].END]=1;
dis[v[i].END]=dis[u]+1;
if(v[i].END==E)return 1;
Q.push(v[i].END);
}
}
}
return 0;
}
int DFS(int S,int E,int a){
if(S==E||a==0)return a;
int flow=0,f;
for(int &i=cur[S];i!=-1;i=v[i].next){
if(dis[v[i].END]==dis[S]+1&&(f=DFS(v[i].END,E,min(a,v[i].cap)))>0){
v[i].cap-=f;
v[i^1].cap+=f;
a-=f;
flow+=f;
if(f==0)break;
}
}
//
if(!flow) dis[S]=-1;
return flow;
}
int Dinic(int S,int E){
int ans=0;
while(BFS(S,E)){
memcpy(cur,first,sizeof(first));
ans+=DFS(S,E,INF);
}
return ans;
}
int main()
{
int n,m;
memset(first,-1,sizeof(first));
scanf("%d%d",&n,&m);
int S=++idIndex,T=++idIndex;
int maxn=0;
for(int i=1;i<=n;i++) maxn=max(maxn,a[i]=read());
for(int i=1;i<=maxn;i++){
Idx[i]=++idIndex;
add(Idx[i],T,m*i*i);
}
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)id[i][j]=++idIndex;
int x;
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
x=read();
if(i==j)x-=a[i],add(id[i][j],Idx[a[i]],INF);
else {
if(id[i+1][j])add(id[i][j],id[i+1][j],INF);
if(id[i][j-1])add(id[i][j],id[i][j-1],INF);
}
if(x>0) ans+=x,add(S,id[i][j],x);
else add(id[i][j],T,-x);
}
}
ans-=Dinic(S,T);
printf("%d\n",ans);
getchar();
getchar();
return 0;
}