题面
题解
首先每种权值只取一次，且不同权值之间有类似于取了xx就必须取xx这种限制，因此我们可以判断这是一个最大权闭合子图问题。
然后我们开始建图
- 对于每个编号为(x),权值为(len)的区间，如果权值为正，则连s ---> x : len ；否则连x ---> t : - len;
- 每个区间([l, r])向([l + 1, r])和([l, r - 1])连(INF)边，表示取([l, r])就必须取这个区间内的所有区间。
- 对于每个区间([i, i]),连向第(i)个寿司,权值为(INF).表示取了这个区间就必须取对应的寿司。
- 对于每个寿司x，连x ---> t : id[x] ； 表示选第x个寿司，可以获得对应的大小为代号的代价。
- 对于每个寿司x, 向对应的寿司代号连(INF)边，表示取了这个寿司就会取走相应的寿司类型。
- 对于每个寿司类型，连x ---> t : m * id[x] * id[x]
然后跑网络流即可。
答案即为所有区间正权之和减去最大流。
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define LL long long
#define N 110
#define AC 50000
#define ac 820000
#define inf 1000000000
int n, m, addflow, x, s, t, all, cnt;
LL ans;
int Head[AC], date[ac], Next[ac], haveflow[ac], tot = 1;
int last[AC], have[AC], c[AC], good[AC], may[AC];
int q[AC], head, tail;
int w[N][N], id[N][N], ID[AC];
inline int read()
{
int x = 0;char c = getchar();bool z = false;
while(c > '9' || c < '0') {if(c == '-') z = true; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
if(!z) return x;
else return -x;
}
inline void upmin(int &a, int b) {if(b < a) a = b;}
inline void upmax(int &a, int b) {if(b > a) a = b;}
inline void add(int f, int w, int S)
{
date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = S;
date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot, haveflow[tot] = 0;
//printf("%d ---> %d : %d
", f, w, S);
}
void pre()
{
n = read(), m = read(), all = n;//一开始给每个代号先建好点
for(R i = 1; i <= n; i ++) ID[i] = may[i] = read();//代号，用于计算代价
for(R i = 1; i <= n; i ++)
for(R j = i; j <= n; j ++)
w[i][j] = read(), id[i][j] = ++ all;//编号，用于网络流建图
s = all + 1, t = s + 1;
}
int half(int x)
{
int l = 1, r = cnt, mid;
while(l < r)
{
mid = (l + r) >> 1;
if(may[mid] == x) return mid;
else if(may[mid] < x) l = mid + 1;
else r = mid - 1;
}
return l;
}
void build()
{
// for(R i = 1; i <= n; i ++) add(i, t, m * i * i);
sort(may + 1, may + n + 1);
for(R i = 1; i <= n; i ++)
if(may[i] != may[i + 1]) may[++ cnt] = may[i];
for(R i = 1; i <= n; i ++) ID[i] = half(ID[i]);//找到这个代号对应的下标
for(R i = 1; i <= cnt; i ++) add(i, t, m * may[i] * may[i]);//第i种代号的编号为i
for(R i = 1; i <= n; i ++)
for(R j = i; j <= n; j ++)
{
if(w[i][j] > 0) add(s, id[i][j], w[i][j]), ans += w[i][j];
else add(id[i][j], t, - w[i][j]);
if(i + 1 <= j) add(id[i][j], id[i + 1][j], inf);
if(i <= j - 1) add(id[i][j], id[i][j - 1], inf);
if(i == j) add(id[i][j], ID[i], inf), add(id[i][j], t, may[ID[i]]);//先向对应的代号连边，表示mx^2的代价...error !!!应该是付出ID[i]的代价，而不是i
}//再向t连边，表示c * x的代价
/*for(R i = 1; i <= n; i ++)
for(R j = i; j <= n; j ++)
printf("id[%d][%d] = %d
", i, j, id[i][j]);*/
}
void bfs()
{
q[++ tail] = t, have[1] = c[t] = 1;
while(head < tail)
{
int x = q[++ head];
for(R i = Head[x]; i; i = Next[i])
{
int now = date[i];
if(!c[now] && haveflow[i ^ 1])
have[c[now] = c[x] + 1] ++, q[++ tail] = now;
}
}
memcpy(good, Head, sizeof(Head));
}
void aru()
{
while(x != s)
{
haveflow[last[x]] -= addflow;
haveflow[last[x] ^ 1] += addflow;
x = date[last[x] ^ 1];
}
ans -= addflow, addflow = inf;
}
void ISAP()
{
bool done = false;
x = s, addflow = inf;
while(c[t] != all + 10)
{
if(x == t) aru();
done = false;
for(R &i = good[x]; i; i = Next[i])
{
int now = date[i];
if(c[now] == c[x] - 1 && haveflow[i])
{
upmin(addflow, haveflow[i]);
last[now] = i, done = true;
x = now; break;
}
}
if(!done)
{
int go = all + 9;
for(R i = Head[x]; i; i = Next[i])
if(c[date[i]] && haveflow[i]) upmin(go, c[date[i]]);
if(!(-- have[c[x]])) break;
have[c[x] = go + 1] ++;
good[x] = Head[x];
if(x != s) x = date[last[x] ^ 1];
}
}
printf("%lld
", ans);
}
int main()
{
// freopen("in.in", "r", stdin);
pre();
build();
bfs();
ISAP();
// fclose(stdin);
return 0;
}