目录

[LOJ 2146][BZOJ 4873][Shoi2017]寿司餐厅

迁移提示
本文迁移自博客园, 原文链接

[LOJ 2146][BZOJ 4873][Shoi2017]寿司餐厅

题意

比较复杂放LOJ题面好了qaq…

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

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

由于餐厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司和鱿鱼寿司一起吃或许会很棒,但和水果寿司一起吃就可能会肚子痛。因此,Kiana 定义了一个综合美味度 $d_{i, 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$ 种寿司各一份,那么这两次取寿司的总美味度为 $d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3}$,其中 $d_{2, 2}$ 只会计算一次。

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

现在 Kiana 想知道,在这家餐厅吃寿司,自己能获得的总美味度(包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。由于她不会算,所以希望由你告诉她。

$n\le 100,a_i\le 1000,m\in{0,1}$

题解

好像是个…裸的最大权闭合子图…最大权闭合子图都不知道果然是学了假的网络流

显然选了一个区间后所有子区间也要选, 选了一个 $d_{i,i}$ 后就要选花费点. 花费点可以拆成两部分, 一部分是 $cx$ 直接从 $d_{i,i}$ 里减去就可以了, 另一部分是 $mx^2$ 需要对于每一个寿司代号都新建一个点来表达.

然后它们之间的制约关系表达成有向边, 求最大权闭合子图就可以了.

果然我还是太菜了…

参考代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>

const int MAXN=1e2+10;
const int MAXV=1e4+10;
const int MAXE=1e6+10;
const int INF=0x7FFFFFFF;

struct Edge{
	int from;
	int to;
	int flow;
	Edge* rev;
	Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* cur[MAXV];
Edge* top=E;

int n;
int m;
int a[MAXN];
bool vis[1010];
int depth[MAXV];
int id[MAXN][MAXN];
int val[MAXN][MAXN];

bool BFS(int,int);
int Dinic(int,int);
int DFS(int,int,int);
void Insert(int,int,int);

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	int s=0,t=1;
	int cnt=1,sum=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			scanf("%d",val[i]+j);
			id[i][j]=++cnt;
			if(i==j)
				val[i][j]-=a[i];
			if(val[i][j]>=0){
				sum+=val[i][j];
				Insert(s,id[i][j],val[i][j]);
			}
			else
				Insert(id[i][j],t,-val[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			Insert(id[i][j],id[i+1][j],INF);
			Insert(id[i][j],id[i][j-1],INF);
		}
	}
	for(int i=1;i<=n;i++)
		Insert(id[i][i],cnt+a[i],INF);
	for(int i=1;i<=n;i++){
		if(!vis[a[i]]){
			vis[a[i]]=true;
			Insert(cnt+a[i],t,m*a[i]*a[i]);
		}
	}
	printf("%d\n",sum-Dinic(s,t));
	return 0;
}

int Dinic(int s,int t){
	int ans=0;
	while(BFS(s,t))
		ans+=DFS(s,INF,t);
	return ans;
}

bool BFS(int s,int t){
	memset(depth,0,sizeof(depth));
	std::queue<int> q;
	q.push(s);
	depth[s]=1;
	cur[s]=head[s];
	while(!q.empty()){
		s=q.front();
		q.pop();
		for(Edge* i=head[s];i!=NULL;i=i->next){
			if(i->flow>0&&depth[i->to]==0){
				depth[i->to]=depth[s]+1;
				cur[i->to]=head[i->to];
				if(i->to==t)
					return true;
				q.push(i->to);
			}
		}
	}
	return false;
}

int DFS(int s,int flow,int t){
	if(s==t||flow<=0)
		return flow;
	int rest=flow;
	for(Edge*& i=cur[s];i!=NULL;i=i->next){
		if(i->flow>0&&depth[i->to]==depth[s]+1){
			int tmp=DFS(i->to,std::min(rest,i->flow),t);
			if(tmp<=0)
				depth[i->to]=0;
			rest-=tmp;
			i->flow-=tmp;
			i->rev->flow+=tmp;
			if(rest<=0)
				break;
		}
	}
	return flow-rest;
}

inline void Insert(int from,int to,int flow){
	top->from=from;
	top->to=to;
	top->flow=flow;
	top->rev=top+1;
	top->next=head[from];
	head[from]=top++;

	top->from=to;
	top->to=from;
	top->flow=0;
	top->rev=top-1;
	top->next=head[to];
	head[to]=top++;
}

https://pic.rvalue.moe/2021/08/02/24963bee27d7f.jpg