#3226. 「USACO 2019.12 Platinum」Greedy Pie Eaters
Summarize
给定$n$个数中$m$个区间，每个区间有一个权值，要求输出总区间权值最大的一个序列使得每个序列不被之前的序列的并集完全覆盖
$1 \le n \le 300,1 \le m \le \frac{n(n-1)}{2}$
感谢@oy的贡献
Solution
区间 DP。考虑对于每个区间，最后一个奶牛一定至少吃掉了一个派。枚举这个派，并进行状态转移即可。
Code
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll a[305][305], f[305][305], g[305][305][305];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int w, l, r;
scanf("%d%d%d", &w, &l, &r);
a[l][r] = 1ll * w;
}
for (int l = 1; l <= n; ++l) {
for (int i = 1, j = i + l - 1; j <= n; ++i, ++j) {
for (int k = i; k <= j; ++k) {
g[i][j][k] = max({ a[i][j], g[i + 1][j][k], g[i][j - 1][k] });
f[i][j] = max(f[i][j], f[i][k - 1] + f[k + 1][j] + g[i][j][k]);
}
}
}
printf("%lld", f[1][n]);
return 0;
}
|