BZOJ 4873 [Shoi2017]寿司餐厅

题目大意

给你N个寿司，然后就……吃……

算了这道题题面我编不下去了，放原题面吧。

Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。

每天晚上，这家餐厅都会按顺序提供 n 种寿司，第 i 种寿司有一个代号 ai 和美味度 d[i,i]，不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的， Kiana也可以无限次取寿司来吃，但每种寿司每次只能取一份，且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段，即 Kiana 可以一次取走第 1; 2 种寿司各一份，也可以一次取走第 2; 3 种寿司各一份，但不可以一次取走第 1; 3 种寿司。

由于餐厅提供的寿司种类繁多，而不同种类的寿司之间相互会有影响：三文鱼寿司和鱿鱼寿司一起吃或许会很棒，但和水果寿司一起吃就可能会肚子痛。因此， Kiana 定义了一个综合美味度 di; j(i < j)，表示在一次取的寿司中，如果包含了餐厅提供的从第 i份到第 j 份的所有寿司，吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间，所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时，不止一个综合美味度会被累加，比如若 Kiana 一次取走了第 1; 2; 3 种寿司各一份，除了 d[1,3] 以外， d[1,2], d[2,3] 也会被累加进总美味度中。

神奇的是， Kiana 的美食评判标准是有记忆性的，无论是单种寿司的美味度，还是多种寿司组合起来的综合美味度，在计入 Kiana 的总美味度时都只会被累加一次。比如，若 Kiana 某一次取走了第 1; 2 种寿司各一份，另一次取走了第 2; 3 种寿司各一份，那么这两次取寿司的总美味度为 d1;1 + d2;2 + d3;3 + d1;2 + d2;3，其中 d2;2 只会计算一次。

奇怪的是，这家寿司餐厅的收费标准很不同寻常。具体来说，如果 Kiana 一共吃过了 c(c > 0) 种代号为 x 的寿司，则她需要为这些寿司付出 mx2 + cx 元钱，其中 m 是餐厅给出的一个常数。

现在 Kiana 想知道，在这家餐厅吃寿司，自己能获得的总美味度（包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度）减去花费的总钱数的最大值是多少。

由于她不会算，所以希望由你告诉她。

这道题当时竟然不会，咕咕咕到现在= =

对于每一个$d_{i,j}$开一个网络流图点。代表$i,i$的点连寿司的种类，因为要累加花费进答案。如果选了这个种类的还有基本费用，也连一下。之后就是重点了——$d_{i,j}$连哪个点啊？岂不是要连接组合数个点= =懵逼

只需要连$i+1,j$和$i,j-1$就好了。

%%%聚聚我真的想不到啊55555

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 110
#define M 20000
#define INF (1<<30)
int n,m,a[N],id[N][N],ref[N],d[N][N],depth[M],cnt,S,T,ans;
int to[500000],nxt[500000],val[500000],head[M],tot=1;
queue<int>q;
inline void AE(int x,int y,int z)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0;
}
bool BFS()
{
	while(!q.empty()) q.pop();
	q.push(S);
	memset(depth,-1,sizeof depth),depth[S]=0;
	while(!q.empty())
	{
		int tmp=q.front();q.pop();
		for(int i=head[tmp];i;i=nxt[i])
			if(val[i]&&depth[to[i]]==-1)
			{
				depth[to[i]]=depth[tmp]+1;
				if(to[i]==T) return true;
				q.push(to[i]);
			}
	}
	return false;
}
int dinic(int pos,int left)
{
	if(pos==T) return left;
	int nleft=left;
	for(int i=head[pos];i;i=nxt[i])
		if(val[i]&&depth[to[i]]==depth[pos]+1)
		{
			int tmp=dinic(to[i],min(nleft,val[i]));
			if(!tmp) depth[to[i]]=-1;
			nleft-=tmp,val[i]-=tmp,val[i^1]+=tmp;
		}
	return left-nleft;
}
int main()
{
	scanf("%d%d",&n,&m),S=0,T=19999;
	for(int i=1;i<=n;++i) scanf("%d",a+i),cnt=max(cnt,a[i]);
	for(int i=1;i<=cnt;++i) AE(i,T,m*i*i);
	for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) scanf("%d",&d[i][j]),id[i][j]=++cnt;
	for(int i=1;i<=n;++i) AE(id[i][i],a[i],INF),d[i][i]-=a[i];
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
		{
			if(i!=j) AE(id[i][j],id[i+1][j],INF),AE(id[i][j],id[i][j-1],INF);
			if(d[i][j]>0) AE(S,id[i][j],d[i][j]),ans+=d[i][j];
			else AE(id[i][j],T,-d[i][j]);
		}
	while(BFS()) ans-=dinic(S,INF);
	printf("%d\n",ans);
	return 0;
}