【USACO19】Greedy Pie Eaters P

· · 题解

  传送门

  这道水题WA了3次才发现 n,m 写反了，大家千万吸取我这个垃圾的教训。

  设 f(i,j) 是在 i..j 块派范围（即不能超出，但也不要求全部吃完） 内的答案。那么最后答案就是 f(1,n)（蒟蒻WA了三次就是输出了 f(1,m))

  我们知道，DP 一般都是考虑 最后一步和上一步的关系，那么对于区间 [i,j]，我们吃掉的最后一个派 可以是 [i,j] 之间的任何一个派，如果最后吃掉的是派 k，那么它对其它的派就不影响了。什么意思，因为选择一头牛要保证这个区间至少还剩下一个派，如果最后吃掉的是第 k 个，那么这头选择的牛的要求范围内其它的派已经无所谓了，不造成影响。那么应该拆成 f(i,k-1) 和 f(k+1,j) 两个区间。又因为 f 数组里的定义是不超过 [i,j]，那么这两个子问题的任意解都不会吃掉第 k 个派。

  那么怎么确定吃掉第 k 个派的这头牛？显然这头牛的要求范围不应超过 i,j，因此设 g(i,j,k) 是 [i,j] 内要求范围有第 k 个派的牛中最大的体重。那么可以拆成 g(i+1,j,k) 和 g(i,j-1,k)，本题就可以做了。

  如果你使用这两个方程转移，你会发现根本不需要判断是不是会出界！，因为不合法状况一定不会RE且为0，符合不合法状况的理想的值。

  然后你会发现 f 也是不需要初始状态的，只有 g 需要。但是 g 的初始状态如果视作 i=j 时不好做，你需要枚举所有奶牛（或者再开一个类似前向星的东西存，太麻烦了）。可能有人已经发现上面的 g 的方程没有考虑 刚好有一个奶牛把整个[i,j]全部吃掉的情况，这种情况就是留待初始化的。

  代码里提供了一种区间DP的不易出错的写法：既然区间DP的转移通常是小区间转移大区间，可以最外层枚举长度，第二层枚举起点，此时终点易得，第三层枚举断点。这个套路就不需要记 i,j 到底哪个正序枚哪个倒序了。（真是为OI赛制量身定做的写法QwQ)

//USACO2019,Platinum
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=310,MAXM=90010;
int f[MAXN][MAXN],g[MAXN][MAXN][MAXN];
int w[MAXM],l[MAXM],r[MAXM];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&w[i],&l[i],&r[i]);
        for(int j=l[i];j<=r[i];j++){
            g[l[i]][r[i]][j] = w[i];
        }
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j = i+len-1;
            for(int k=i;k<=j;k++){
                g[i][j][k] = max(g[i][j][k],max(g[i+1][j][k],g[i][j-1][k]));
            }
        }
    }
    for(int len = 1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j = i+len-1;
            for(int k=i;k<j;k++){
                f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]);
            }
            for(int k=i;k<=j;k++){
                f[i][j] = max(f[i][j],g[i][j][k] + f[i][k-1] + f[k+1][j]);
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}