题意：
分析：
- 暴力：
状压 (O(2^n*n^2)) 期望得分 50pts
-
正解：
-
前置芝士：
最大权闭合子图：对于一堆物品，选择会得到一个价值，存在一些依赖关系限制
构建方式：
- 首先统计所有正权价值和 (sum)
- 对于正权价值的物品，和原点连一条流量为 价值 的边，对于负权的物品，和汇点连一条流量为 -价值 的边
- 对于依赖关系选x就必须选y，那么 (x) 向 (y) 连一条流量为正无穷的边
- 对于建出的图跑一遍最小割，权值和最大为 (sum-maxflow)
证明：
我们在网络流上的流量就代表需要扔掉的物品权值，若断开与汇点连的边表示选择该物品，如果断开与源点连的边表示不选该物品，这样对于正权物品不和汇点建边表示选择它不需要消耗代价，对于负权物品不和源点连边表示不选它不需要减少代价，对于依赖关系，如果选择 (x) ，断掉 (x o t)，不选 (y) 断掉 (s o y) ,那么还存在一条增广路 (s o x o y o t)不符合题意
对于这个题来说，由于依赖关系和每种价值只算一次，我们可以发现这是最大权闭合子图。那么我们把每一段寿司看成一种物品，美味度看成一种物品的权值。那么选择 (d_{i,j}) 就必须选择 (d_{i-1,j}) 和 (d_{i+1,j})，这就是一种依赖关系，这样我们就解决了收益的问题
现在我们考虑如何减去花费，对于 代价 (mx^2+cx) 我们可以看做，每吃一个 (x) 类型的寿司花费为 (x) ，吃过 (x) 类型的寿司还需要额外再收 (x^2) 的费用
对于 (d_{i,i}) 代表选择了 (a_i) 类型的寿司，需要花费 (a_i) ,同时还需要额外付一些费用，所以我们把每种寿司类型也看成一种物品，代价为 (x^2) ，存在一种依赖关系就是选择 (d_{i,i}) 就必须选择 (a_i)
代码：
难点在于建模，代码没什么难度
#include<bits/stdc++.h>
#define inl inline
#define reg register
using namespace std;
namespace zzc
{
typedef long long ll;
inl ll read()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 2e4+5;
const int maxm = 1e6+5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll n,m,st,ed,ans,cnt=1,tot,lim;
ll head[maxn],cur[maxn],a[maxn],dep[maxn],id[105][105],f[105][105];
queue<ll> q;
struct edge
{
ll to,nxt,w;
}e[maxm];
void add(ll u,ll v,ll w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void add_edge(ll u,ll v,ll w)
{
add(u,v,w);add(v,u,0);
}
bool bfs()
{
for(reg int i=1;i<=tot;i++) dep[i]=-1;
dep[st]=0;q.push(st);
while(!q.empty())
{
ll u=q.front();q.pop();
for(reg ll i=head[u];i;i=e[i].nxt)
{
ll v=e[i].to;
if(e[i].w&&dep[v]==-1)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[ed]!=-1;
}
ll dfs(ll u,ll flow)
{
if(u==ed) return flow;
ll used=0,w;
for(reg ll &i=cur[u];i;i=e[i].nxt)
{
ll v=e[i].to;
if(e[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(flow-used,e[i].w));
e[i].w-=w;
e[i^1].w+=w;
used+=w;
if(used==flow) return used;
}
}
if(!used) dep[u]=-1;
return used;
}
ll dinic()
{
ll res=0;
while(bfs())
{
memcpy(cur,head,sizeof(cur));
res+=dfs(st,inf);
}
return res;
}
void work()
{
n=read();m=read();st=1;ed=2;tot=2;
for(reg int i=1;i<=n;i++) a[i]=read(),lim=max(lim,a[i]);
for(reg int i=1;i<=n;i++) for(reg int j=i;j<=n;j++) f[i][j]=read(),id[i][j]=++tot;
for(reg int i=1;i<=n;i++) for(reg int j=i;j<=n;j++)
{
ll cost=f[i][j];
if(i==j)
{
if(m) add_edge(id[i][j],tot+a[i],inf);
cost-=a[i];
}
else
{
add_edge(id[i][j],id[i+1][j],inf);
add_edge(id[i][j],id[i][j-1],inf);
}
if(cost>0) add_edge(st,id[i][j],cost),ans+=cost;
if(cost<0) add_edge(id[i][j],ed,-cost);
}
if(m) for(reg int i=1;i<=lim;i++) add_edge(++tot,ed,i*i);
printf("%lld
",ans-dinic());
}
}
int main()
{
zzc::work();
return 0;
}