Luogu

LOJ

分析

数组开小 -> 100->40 -> 身败名裂

先考虑没有费用的情况，显然是最大权闭合子图模型（选了 $[i,j]$ 就必须选它的所有子区间）。因此对于每个 $[i,j]$，如果 $d_{i,j}$ 为正则从源点向它连容量为 $d_{i,j}$ 的边，否则从它向汇点连容量为 $-d_{i,j}$ 的边，然后对于每个 $[i,j]$ 向它的子区间连容量为 $+\infty$ 的边，用总正权值减去最小割即为答案。

然而这个东西边数是 $\mathcal{O}(n^4)$ 的，瓶颈在 $[i,j]$ 向子区间连边那一部分。但是仔细思考一下可以发现，我们只需要向 $[i,j-1]$ 和 $[i+1,j]$ 连边就好了。

现在加入费用。先考虑 $m=0$ 的情况，即选了寿司 $i$ 就会产生 $a_i$ 的费用。此时我们只需要从 $[i,i]$ 向汇点连容量为 $a_i$ 的边即可。

再考虑 $m\neq 0$ 时怎么做。此时相当于选了一个 $a_i$ 就会产生 $ma_i^2$ 的费用。我们对每个 $a_i$ 建一个点，从每个 $[i,i]$ 向对应的 $a_i$ 连容量为 $+\infty$ 的边，然后每个 $a_i$ 向汇点连容量为 $ma_i^2$ 的边即可。。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10,L=1000+10;
const int V=20000+10,E=100000+10;
const int inf=0x3f3f3f3f;

int n,m,a[N],d[N][N],id[N][N],ida[L],tot=0;

struct edge { int v,w,nxt; } e[E<<1];
int head[V];
void addEdge(int u,int v,int w) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,head[v]},head[v]=cnt;
}

int lv[N],S,T;
int bfs() {
    memset(lv,0,sizeof(lv)); queue<int> Q;
    Q.push(S),lv[S]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&!lv[v]) lv[v]=lv[u]+1,Q.push(v);
        }
    }
    return lv[T]!=0;
}
int dfs(int u,int cpflow) {
    if (!cpflow||u==T) return cpflow;
    int addflow=0;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (e[i].w&&lv[v]==lv[u]+1) {
            int t=dfs(v,min(cpflow,e[i].w));
            e[i].w-=t,e[i^1].w+=t;
            addflow+=t,cpflow-=t;
            if (!cpflow) break;
        }
    }
    if (!addflow) lv[u]=0;
    return addflow;
}
int dinic() { int mf=0; 
    while (bfs()) mf+=dfs(S,inf);
    return mf;
}

int main() {
    n=read(),m=read(); int ans=0;
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;++j)
            d[i][j]=read(),id[i][j]=++tot;
    S=0,T=++tot;
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;++j) {
            if (d[i][j]>=0) addEdge(S,id[i][j],d[i][j]),ans+=d[i][j];
            else addEdge(id[i][j],T,-d[i][j]);
        }
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j) {
            addEdge(id[i][j],id[i+1][j],inf);
            addEdge(id[i][j],id[i][j-1],inf);
        }
    for (int i=1;i<=n;++i) addEdge(id[i][i],T,a[i]);
    if (m) {
        for (int i=1;i<=n;++i)
            if (!ida[a[i]]) ida[a[i]]=++tot,addEdge(tot,T,a[i]*a[i]);
        for (int i=1;i<=n;++i) addEdge(id[i][i],ida[a[i]],inf);
    }
    printf("%d\n",ans-dinic());
    return 0;
}