AK-dream

题目描述

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, m$,分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。
第二行包含 $n$ 个正整数,其中第 $k$ 个数 $a_k$ 表示第 $k$ 份寿司的代号。
接下来 $n$ 行,第 $i$ 行包含 $n - i + 1$ 个整数,其中第 $j$ 个数 $d_{i, i+j-1}$ 表示吃掉寿司能获得的相应的美味度,具体含义见问题描述。

输出格式

输出共一行包含一个正整数,表示 Kiana 能获得的总美味度减去花费的总钱数的最大值。

题解

注意一下 吃寿司的代价和你吃了多少种有关,而不是吃了多少个。。。

第一眼看是DP 然而很快就发现有时候取重叠的区间可能更优 于是DP就没有了

而且数据范围这么小 怎么看都是网络流 但是蒟蒻不会建图

回头看了一下题解 发现其实还挺套路的。。。

一个经典的最小割模型(好像还叫什么最大权闭合子图?)

我们对于每个寿司区间都建立一个点 如果最小割割完后这个点在源点的联通块就表示我们选了这个区间 如果在汇点的联通块就表示没选

  1. 对于有着正美味度的区间$[i,j]$,从源点向它连一条流量为美味度$d_{i,j}$的边,表示不选这个点要付出$d_{i,j}$的代价
  2. 对于有着负美味度的区间$[i,j]$,从它向汇点连一条流量为$-d_{i,j}$的边,表示选了这个点要付出$-d_{i,j}$的代价

因为如果选了$[i,j]$,必然选了它的所有子区间,所以我们对于每个区间$[i,j]$:

  1. 从$[i,j]$向$[i+1,j]$和$[i,j+1]$分别连一条流量为$inf$的边,表示选了$[i,j]$必须选剩下两个

然后看看每个寿司的选择代价要怎么处理

我们同样对于每个单个的寿司建一个点

  1. 对于每个寿司点$i$,向汇点连一条流量为代号$a_i$的边 表示选过这个寿司要付出$a_i$的代价
  2. 从区间点$[i,i]$向寿司点$i$连一条流量为$inf$的边 表示选了前者必须选后者

最后看看那个$mx^2$的代价怎么处理:

如法炮制,我们对于每个寿司代号建一个点

  1. 对于代号点$x$,向汇点连一条流量为$mx^2$的边
  2. 从每个代号为$x$的寿司点 向这个代号点$x$连一条$inf$ 表示选了那个寿司就要付出代号的$mx^2$代价

最小割等于最大流 用dinic求出

然后我们注意到类型1的边是”不选它会付出$d_{i,j}$”的代价 所以初始时我们把答案设置成所有正的美味度之和

然后最终答案就是 所有正的美味度之和 减去最小割

代码

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
#include <bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &num) {
T x = 0, _f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') _f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * _f;
}

const int inf = 0x7fffffff;
int n, m, s, t, c[205], val[205][205], d[12005], ans;
int now[12005], head[12005], pre[500005], to[500005], flow[500005], sz = 1;
int ind[205][205], indtp[1005], tot;
bool vis[1005];

inline void addedge(int u, int v, int w) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v; flow[sz] = w;
}

bool bfs() {
memset(d, 0, sizeof(d));
queue<int> q;
q.push(s); d[s] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (flow[i] > 0 && d[y] == 0) {
d[y] = d[x] + 1;
q.push(y);
}
}
}
return (d[t] != 0);
}

int dfs(int x, int cur) {
if (x == t || cur <= 0) return cur;
int rest = cur;
for (int i = now[x]; i; i = pre[i]) {
now[x] = i; int y = to[i];
if (flow[i] > 0 && d[y] == d[x] + 1) {
int tmp = dfs(y, min(rest, flow[i]));
if (tmp <= 0) d[y] = 0;
flow[i] -= tmp; flow[i^1] += tmp;
rest -= tmp;
if (rest <= 0) break;
}
}
return cur - rest;
}

int dinic() {
int ret = 0;
while (bfs()) {
memcpy(now, head, sizeof(now));
ret += dfs(s, inf);
}
return ret;
}

void preind() {
s = 0;
for (int i = 1; i <= n; i++) {
if (!vis[c[i]]) {
indtp[c[i]] = ++tot;
vis[c[i]] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
ind[i][j] = ++tot;
}
}
t = ++tot;
}

int main() {
read(n); read(m);
tot = n;
for (int i = 1; i <= n; i++) {
read(c[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
read(val[i][j]);
}
}
preind();
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
if (val[i][j] >= 0) {
addedge(s, ind[i][j], val[i][j]); //边类型1
addedge(ind[i][j], s, 0);
ans += val[i][j];
} else {
addedge(ind[i][j], t, -val[i][j]); //边类型2
addedge(t, ind[i][j], 0);
}
if (i != j) {
addedge(ind[i][j], ind[i][j-1], inf); //边类型3
addedge(ind[i][j-1], ind[i][j], 0);
addedge(ind[i][j], ind[i+1][j], inf);
addedge(ind[i+1][j], ind[i][j], 0);
}
}
}
for (int i = 1; i <= n; i++) {
addedge(ind[i][i], i, inf); addedge(i, ind[i][i], 0); //边类型5
addedge(i, t, c[i]); addedge(t, i, 0); //边类型4
addedge(i, indtp[c[i]], inf); addedge(indtp[c[i]], i, 0); //边类型7
}
for (int i = 1; i <= 1000; i++) {
if (vis[i] && m) {
addedge(indtp[i], t, m * i * i); addedge(t, indtp[i], 0); //边类型6
}
}
printf("%d\n", ans - dinic());
return 0;
}

 评论