题解 P5851 【[USACO19DEC]Greedy Pie Eaters P】
wylt
2020-02-20 14:54:50
USACO 2019 December 铂金组T1 Greedy Pie Eaters
原题面（英文）：[http://www.usaco.org/index.php?page=viewproblem2&cpid=972](http://www.usaco.org/index.php?page=viewproblem2&cpid=972)
官方题解（英文）：[http://www.usaco.org/current/data/sol_pieaters_platinum_dec19.html](http://www.usaco.org/current/data/sol_pieaters_platinum_dec19.html)
------------
### 题意简述
有 M 头牛，N 个派，每头牛都有体重和吃派的范围，分别用 $w$, $l$, $r$ 表示，
每头牛按顺序轮流吃派，且牛 i 会吃掉此时 $\left[l_{i}\ ,r_{i}\right]$ 的所有派。
我们需要求出每头牛按顺序吃完后，满足所有牛都至少吃到一个的 $\max\sum\limits_{i=c1}^{ck}w_i$ 。
其中 $N\le300,\ w_{i}\le10^6$ 。
### 题目分析
容易看出本题是一道区间求极值的问题，而区间 dp 就刚好可以解决此类问题，再看数据范围 $N\le300$, 所以我们可以朝区间 dp 这方面思考一下。
那么我们可以得到一个基本思路， $f(i,j)=\max(\ f(i,j),\ f(i,k-1)+f(k+1,j)+p(k,i,j)\ )$ 。
其中 $i,j,k$ 为下标，表示第 $i$ 个派 ；
$f(i,j)$ 表示此时 $\left[i\ ,j\right]$ 已被吃完的最大 $\sum\limits_{}^{}w$ ；
$p(k,i,j)$ 表示当 k 还未被吃时能吃掉 k 且 $i\le l\le k\le r\le j$ 的最大的一个 $w$ ；
所以转移方程可以理解为通过合并 $f(i,k-1)+f(k+1,j)$ 更新 $f(i,j)$ 的值，
而**第一个问题**就来了：为什么是 $f(i,k-1)+f(k+1,j)$ 而不是 $f(i,k)+f(k+1,j)$ 呢？
因为题目要求每头牛都**至少吃到一个**，所以在合并时就必须满足 k 还未被吃，
而 $f(i,k)+f(k+1,j)$ 就可能存在两部分都已经被吃完的尴尬情况。
**第二个问题**，为什么 $p(k,i,j)$ 中 $i\le l\le k\le r\le j$ 呢？
因为现在我们要求合并时拥有最大 $w$ 的一个能吃掉第 k 个派的牛，
所以 k 必须在这头牛的 $l,r$ 之间，且不能把 $\left[i\ ,j\right]$ 以外的派吃掉，而影响了后面的更新
**第三个问题**，也是最难的一个问题，就是如何求出 $p(k,i,j)$。
我们知道， $p(k,i,j)$ 肯定是可以先预处理出来的，其实思路也基本就是区间 dp 的思路，
即 $p(k,i-1,j)=\max(\ p(k,i-1,j),\ p(k,i,j)\ )$ ；
$p(k,i,j+1)=\max(\ p(k,i,j+1),\ p(k,i,j)\ )$。
也就是通过已经得出的一个个向外更新，最终扩展到整个序列。
**温馨提示（血的教训）**：
我们可以发现下面代码的两个更新循环有许多不一样，但改变任何一个的顺序都会 wa 掉。
对于区间 dp 千万要注意循环的顺序，一般循环有三层，分为枚举 $i,j$ 和他们的合并点 $k$ ，
有两种顺序为 $i->j->k$ 和 $k->i->j$ ，
也就是 $k$ 的出现顺序不同，我们可以根据模拟的方法推出哪种顺序不对，
只要发现会用到未更新过的点更新自己就是错误的，一般很快就可以判断出来。
其次还要注意是从 $1$ 枚举到 $N$ 还是要反过来从 $N$ 枚举到 $1$ ，方法和上面一样，就不多说了。
------------
### 代码
代码和官方题解的思路基本一样，但可读性可能会好一点。
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int f[305][305];
int p[305][305][305];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int w,l,r;
cin>>w>>l>>r;
for(int j=l;j<=r;j++){
p[j][l][r]=w;//由于没有两头奶牛喜欢吃相同范围的派，可以不用比较大小，直接赋值即可
}
}
for(int k=1;k<=n;k++){
for(int i=k;i>=1;i--){
for(int j=k;j<=n;j++){
//if为了防止下标超过[1,n]
if(i!=1){
p[k][i-1][j]=max(p[k][i][j],p[k][i-1][j]);
}
if(j!=n){
p[k][i][j+1]=max(p[k][i][j],p[k][i][j+1]);
}
}
}
}
for(int i=n;i>=1;i--){
for(int j=i;j<=n;j++){
for(int k=i;k<j;k++){//k!=j是因为底下的f(k+1,j)
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);//先把f(i,j)用前几次的新数据更新
}
for(int k=i;k<=j;k++){
f[i][j]=max(f[i][j],(k!=i?f[i][k-1]:0)+(k!=j?f[k+1][j]:0)+p[k][i][j]);
//同样要防止出现f(i,j)中，i>j的情况
}
}
}
cout<<f[1][n];
return 0;
}
```