LibreOJ 3226 「USACO 2019 · December」Greedy Pie Easters

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

设 ai,j 表示吃的派编号为 [i,j] 的牛的体重，如果没有就当成 0。
设 gi,k,j=maxi≤l≤k≤r≤jal,r。
设 fi,j 表示吃完 [i,j] 的派的最大体重，那么转移时，考虑枚举最后吃的派的编号为 k，则 fi,j=maxi≤k≤j(fi,k−1+fk+1,j+gi,k,j)

代码：

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