题目概述

题目太复杂了QAQ，自己去看吧……吃我传送门。

解题报告

很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件，发现带有很多“强制”操作，比如吃了 $[L,R]$ ，里面的所有子区间贡献都会被算上，且 $[L,R]$ 中所有寿司种类都要付钱……

由此我们想到这是最大权闭合图，分一下类，有“代号”，“寿司”，“区间”这三种点，然后开始建图：

寿司 $i$ (区间 $[i,i]$ ) $\to$ 代号 $a_i$ ：容量 $+\infty$ 。

区间 $[L,R]\to [L+1,R],[L,R-1]$ ：容量 $+\infty$ 。

代号 $i\to T$ ：容量 $mi^2$ 。

寿司 $i$ 点权 $d[i][i]-a[i]$ ：根据点权正负建边。

区间 $[L,R]$ 点权 $d[L][R]$ ：根据点权正负建边。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100,maxt=6050,maxm=maxt*3,MAXINT=((1<<30)-1)*2+1;

int n,m,a[maxn+5],d[maxn+5][maxn+5],ID[maxn+5][maxn+5],S=0,T=maxt+1;
int E,lnk[maxt+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5];
int cur[maxt+5],que[maxt+5],ti,vis[maxt+5],dis[maxt+5],ans;
pair<int,int> e[(maxm<<1)+5];

inline void Add(int x,int y,int z){
    son[E]=y;nxt[E]=lnk[x];e[E]=mp(0,z);lnk[x]=E++;
    son[E]=x;nxt[E]=lnk[y];e[E]=mp(0,0);lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
    return vis[t]==ti;
}
int Dfs(int x,int gl,int MIN=MAXINT){
    if (x==gl||!MIN) return MIN;int f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],gl,min(MIN,e[j].sc-e[j].fr)))){
            f+=now;e[j].fr+=now;e[j^1].fr-=now;
            if (!(MIN-=now)) break;
        }
    return f;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);E=0;memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
            scanf("%d",&d[i][j]),ID[i][j]=++ID[0][0];
    for (int i=1;i<=n;i++) Add(ID[i][i],T-a[i],MAXINT);
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            Add(ID[i][j],ID[i+1][j],MAXINT),Add(ID[i][j],ID[i][j-1],MAXINT);
    for (int i=1;i<=1000;i++) Add(T-i,T,m*i*i);
    for (int i=1;i<=n;i++)
        d[i][i]-a[i]<0?Add(ID[i][i],T,a[i]-d[i][i]):(ans+=d[i][i]-a[i],Add(S,ID[i][i],d[i][i]-a[i]));
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            d[i][j]<0?Add(ID[i][j],T,-d[i][j]):(ans+=d[i][j],Add(S,ID[i][j],d[i][j]));
    while (Bfs(S,T)) memcpy(cur,lnk,sizeof(lnk)),ans-=Dfs(S,T);
    return printf("%d\n",ans),0;
}