分析
数组开小 -> 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;
}