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]);
}