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;
}