Description:

$N$ 种寿司，每次可以取连续的一段，每一段都有价值，取一段时可以将这一段的所有子段的价值都取，同一种可以取多个，但任意区间的价值只能取一次，每种寿司都有一个编号 $A_i$ ，如果编号为 $A_k$ 的寿司取了 $S_k$ 次，则这些寿司的花费为 $m\times A_k^2+S_k\times A_k$ ，求价值 $-$ 花费的最小值。

$1\le N \le 100$

Solution:

任意价值只能取一次，联想到最大权闭合子图，可以发现如果取了 $d[i][j]$ ，则 $d[i+1][j]$ 和 $d[i][j-1]$ 必须选，如果 $d[i][i]$ 选了，则 $-A_i$ 和 $-A_i^2\times m$ 必须选，但 $-A_i$ 每次都要选但 $-A_i\times m$ 只用选一次，所以每个 $d[i][j]$ 先减掉 $A_i$ ，然后做最大权闭合子图即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n,m;

int s,t;

#define MAXN 1010

int a[MAXN];

bool v[MAXN];

int tr[MAXN];

int d[MAXN][MAXN];

int to(int i,int j){return (i - 1) * n + j;}

long long sum = 0; 

struct edge

{

	int to,nxt,f;

}e[MAXN * MAXN * 2 * 2 + MAXN * 2];

int edgenum = 0;

int lin[MAXN * MAXN + MAXN];

void add(int a,int b,int c)

{

	e[edgenum].to = b;e[edgenum].f = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

void init()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = i;j <= n;++j)

		{

			scanf("%d",&d[i][j]);

		}

	}

	return;

}

void build()

{

	s = n * n + n + 1,t = s + 1;

	memset(v,false,sizeof(v));

	sum = 0;

	for(int i = 1;i <= n;++i)

	{

		if(!v[a[i]])

		{

			add(n * n + i,t,a[i] * a[i] * m);

			tr[a[i]] = i;

			v[a[i]] = true;

		}

		add(to(i,i),tr[a[i]] + n * n,INF);

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = i;j <= n;++j)

		{

			if(i == j)

			{

				d[i][j] -= a[i];

			}

			if(d[i][j] > 0)sum += d[i][j];

			if(j > 1)add(to(i,j),to(i,j - 1),INF);

			if(i < j)add(to(i,j),to(i + 1,j),INF);

			if(d[i][j] > 0)add(s,to(i,j), d[i][j]);

			if(d[i][j] < 0)add(to(i,j),t,-d[i][j]);

		}

	}

	return;

}

int ch[MAXN * MAXN + MAXN];

bool bfs()

{

	memset(ch,-1,sizeof(ch));

	queue<int> q;

	q.push(s);

	ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(f - r,e[i].f));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

long long dinic()

{

	long long ans = 0,r;

	while(bfs())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	init();

	build();

	cout << sum - dinic() << endl;

	return 0;

}