LibreOJ 3226 「USACO 2019 · December」Greedy Pie Easters

听说最优解是每头牛最多吃一个派。
然后看这个数据范围就感觉是区间 DP。

\(a_{i,j}\) 表示吃的派编号为 \([i,j]\) 的牛的体重,如果没有就当成 \(0\)
\(g_{i,k,j} = \max\limits_{i\le l\le k\le r\le j} a_{l,r}\)
\(f_{i,j}\) 表示吃完 \([i,j]\) 的派的最大体重,那么转移时,考虑枚举最后吃的派的编号为 \(k\),则 \[ f_{i,j} = \max\limits_{i\le k\le j}(f_{i,k-1}+f_{k+1,j}+g_{i,k,j}) \]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 300;
int n,m;
int a[N + 5][N + 5],f[N + 5][N + 5],g[N + 5][N + 5][N + 5];
int main()
{
scanf("%d%d",&n,&m);
int w,l,r;
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",&w,&l,&r),a[l][r] = w;
for(register int i = n;i;--i)
for(register int j = i;j <= n;++j)
for(register int k = i;k <= j;++k)
g[i][k][j] = max(max(g[i + 1][k][j],g[i][k][j - 1]),a[i][j]),
f[i][j] = max(f[i][j],f[i][k - 1] + f[k + 1][j] + g[i][k][j]);
printf("%d\n",f[1][n]);
}