http://www.lydsy.com/JudgeOnline/problem.php?id=4873
https://www.luogu.org/problemnew/show/P3749
打眼一看是道网络流。
但是只能说自己网络流学艺不精啊，这样的题还得借助题解……
我们考虑令一段区间的价值即为d[i][j]，则取一段区间[i,j]，就必须得取[i+1,j]和[i,j-1]，以此类推。
但是我们还有费用呢……
思考只要取了一种数，我们就一定会付出m*x*x的代价，所以我们对编号（设为i）建点，点权为-m*i*i。
再思考我们只要取了某个编号为i的寿司，必须付出i的代价，所以对每个寿司（即区间[i,i]）的点权-i
这就是最大权闭合子图的模型了，把区间看成点，正点权连向源点，负点权连向汇点，点和点之间连的INF的边。
（但愿省选无悔）
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
const int M=;
const int INF=1e9;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int nxt,to,w;
}edge[M];
int head[N],cnt=-,S,T;
void add(int u,int v,int w){
edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt;
}
int lev[N],cur[N],dui[N];
bool bfs(int m){
int r=;
for(int i=;i<=m;i++){
lev[i]=-;
cur[i]=head[i];
}
dui[]=S,lev[S]=;
int u,v;
for(int l=;l<=r;l++){
u=dui[l];
for(int e=head[u];e!=-;e=edge[e].nxt){
v=edge[e].to;
if(edge[e].w>&&lev[v]==-){
lev[v]=lev[u]+;
r++;
dui[r]=v;
if(v==T)return ;
}
}
}
return ;
}
int dinic(int u,int flow,int m){
if(u==m)return flow;
int res=,delta;
for(int &e=cur[u];e!=-;e=edge[e].nxt){
int v=edge[e].to;
if(edge[e].w>&&lev[u]<lev[v]){
delta=dinic(v,min(edge[e].w,flow-res),m);
if(delta>){
edge[e].w-=delta;
edge[e^].w+=delta;
res+=delta;
if(res==flow)break;
}
}
}
if(res!=flow)lev[u]=-;
return res;
}
int n,m,d[][],a[],tot,num[][],ans;
int main(){
memset(head,-,sizeof(head));
n=read(),m=read();
for(int i=;i<=n;i++)a[i]=read();
S=,T=tot=;
for(int i=;i<=;i++){
add(i,T,m*i*i);add(T,i,);
}
for(int i=;i<=n;i++){
for(int j=;j<=n-i+;j++){
num[i][i+j-]=++tot;
d[i][i+j-]=read();
}
}
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
int v=d[i][j];
if(i==j){
v-=a[i];
add(num[i][j],a[i],INF);
add(a[i],num[i][j],);
}else{
add(num[i][j],num[i+][j],INF);
add(num[i+][j],num[i][j],);
add(num[i][j],num[i][j-],INF);
add(num[i][j-],num[i][j],);
}
if(v>){
ans+=v;
add(S,num[i][j],v);
add(num[i][j],S,);
}else{
add(num[i][j],T,-v);
add(T,num[i][j],);
}
}
}
while(bfs(tot))ans-=dinic(S,INF,T);
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++