题目
题解
题目要求的就是$\sum d-(mx^2+cx)$的最大值
看到这玩意我就想到了最大权闭合子图，直接建边$((i,i),T,a_i),(a_i,T,{a_i}^2)$，然后分值的正负每个区间连$S/T$，区间之间连一下$\inf$边即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5,N=105,inf=1e9;
struct p{
int x,y,d;
}c[MAX];
int n,m,num=1,cnt,T,ans;
int h[MAX],H[MAX],use[MAX],d[MAX],a[MAX],qu[MAX];
int id[N][N];
int read()
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
void add(int x,int y,int d)
{
c[++num]=(p){h[x],y,d},h[x]=num;
c[++num]=(p){h[y],x,0},h[y]=num;
}
bool bfs()
{
memset(d,0,sizeof(d));
int hl=1,tl=d[0]=1;
while(hl<=tl)
{
int tt=qu[hl++];
for(int i=h[tt],y;i;i=c[i].x)
if(c[i].d&&!d[y=c[i].y])
{
d[y]=d[tt]+1,qu[++tl]=y;
if(y==T) return 1;
}
}
return 0;
}
int dfs(int x=0,int dix=inf)
{
if(x==T||!dix) return dix;
int sum=0;
for(int &i=H[x],dis,y;i;i=c[i].x)
if(d[y=c[i].y]==d[x]+1&&c[i].d)
{
dis=dfs(y,min(dix,c[i].d));
if(dis)
{
c[i].d-=dis,c[i^1].d+=dis,sum+=dis,dix-=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-2;
return sum;
}
int Dinic()
{
int tot=0,D;
while(bfs())
{
memcpy(H,h,sizeof(h));
while(D=dfs()) tot+=D;
}
return tot;
}
int main()
{
n=read(),m=read(),T=n*n+n+1;
for(int i=1;i<=n;++i)
{
a[i]=read();
if(!use[a[i]]&&m) add(use[a[i]]=++cnt,T,a[i]*a[i]);
for(int j=i;j<=n;++j)
id[i][j]=++cnt;
add(id[i][i],T,a[i]),add(id[i][i],use[a[i]],inf);
}
for(int i=1;i<=n;++i)
for(int j=i,x;j<=n;++j)
{
x=read();
if(x>0) add(0,id[i][j],x),ans+=x;
else add(id[i][j],T,-x);
if(i!=j) add(id[i][j],id[i+1][j],inf),add(id[i][j],id[i][j-1],inf);
}
return printf("%d",ans-Dinic()),0;
}
