题意

思路

由得到的权值不重复可以看出这是一道最大权闭合子图问题 （反正我是没看出来），即最小割

可以看出，如果得到了权值\(d_{l,r}\)，可以且必须得到权值\(d_{x,y},(l\leq x \leq y\leq r)\)，必须要花费\([l,r]\)这一区间的代价，于是可以得到建图方法

将一个区间看做一个点

1. \(d_{l,r}>0\)，\(ans\) \(+=d_{l,r}\)，\(S\)向它连边，边权为\(d_{l,r}\)，割掉这条边表示不选择这个值，产生\(d_{l,r}\)的代价

2. \(d_{l,r}\leq 0\)，它向\(T\)连边，边权为\(-d_{l,r}\)，割掉这条边表示选择这个值，会产生\(-d_{l,r}\)的代价

3. 每个区间向它包含的小区间连长度为INF的边，和上面连的边一起表示要么选择放弃正的权值，要么选择负的权值；优化：显然边会重复，区间\([l,r]\)只用向\([l+1,r]\)和\([l,r-1]\)连边即可

4. 每个区间向它所包含的所有寿司编号连边，权值为INF，所有的寿司编号向\(T\)连边，权值为\(a[i]\)，表示选择了这个区间的正值就得付出\(a[i]\)的代价；优化：也有重复的连边，\([l,r]\)只用向\(l\)和\(r\)连边即可

5. 每个编号\(i\)向其代号\(a[i]\)连权值为INF的边，代号\(a[i]\)向\(T\)连权值为\(m*a[i]*a[i]\)的边，原理同上

此时的最小割即为花费的代价，\(ans=ans-dinic()\)

Code

#include
    
     #define N 50005#define INF 100000000using namespace std;int n,m,s,t,dep[N];int a[N];bool vis[N];struct Edge{    int next,to,flow;}edge[N*6];int head[N],cur[N],cnt=1;inline void add_edge(int from,int to,int flow){    edge[++cnt].next=head[from];    edge[cnt].to=to;    edge[cnt].flow=flow;    head[from]=cnt;}void add(int from,int to,int flow){    add_edge(from,to,flow);    add_edge(to,from,0);}template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}int get_id(int i,int j) {return (i-1)*n+j;}bool bfs(){    queue
      
        q;    memset(dep,0,sizeof(dep));    memcpy(cur,head,sizeof(head));    q.push(s); dep[s]=1;    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].to;            if(edge[i].flow<=0||dep[v]) continue;            dep[v]=dep[u]+1;            q.push(v);            if(v==t) return true;        }    }    return false;}int dfs(int rt,int rest){    if(rt==t) return rest;    int used=0;    for(int i=cur[rt];i&&used
       
        0)        {            int k=dfs(v,min(edge[i].flow,rest-used));            if(!k) {dep[v]=0;continue;}            edge[i].flow-=k;            edge[i^1].flow+=k;            used+=k;        }    }    return used;}int dinic(){    int ret=0;    while(bfs()) ret+=dfs(s,INF);    return ret;}int main(){//  freopen("sushi.in","r",stdin);//  freopen("sushi.out","w",stdout);    int ans=0;    read(n);read(m);    s=0;t=N-1;    for(int i=1;i<=n;++i)    {        read(a[i]);        if(!vis[a[i]]) add(n*(n+1)+a[i],t,m*a[i]*a[i]);        vis[a[i]]=1;        add(n*n+i,n*(n+1)+a[i],INF);        add(n*n+i,t,a[i]);    }    for(int i=1;i<=n;++i)    {        for(int j=1;j<=n-i+1;++j)        {            int b; read(b);            if(b>=0)            {                ans+=b;                add(s,get_id(i,i+j-1),b);            }            else add(get_id(i,i+j-1),t,-b);        }    }    for(int i=1;i<=n;++i)    {        for(int j=i;j<=n;++j)        {            if(i==j)            {                add(get_id(i,j),n*n+i,INF);                continue;            }            add(get_id(i,j),get_id(i+1,j),INF);            add(get_id(i,j),get_id(i,j-1),INF);            add(get_id(i,j),n*n+i,INF);            add(get_id(i,j),n*n+j,INF);        }    }    cout<