题解 P5851 【[USACO19DEC]Greedy Pie Eaters】
Purple_wzy
2020-01-05 13:33:34
#### A Greedy Pie Eaters
题目：http://www.usaco.org/index.php?page=viewproblem2&cpid=972
题目大意：有n个派，m头牛，每头牛有一个区间[l,r]和一个权值w。
没有两头牛有相同的[l,r]。
你需要选择一些牛，按一定顺序吃派。每头牛会吃完他的那个区间的所有派。
问在满足每头牛都至少有一个派吃的情况下，能获得的最大权值是多少。
n<=300,m<=45000
题解：n很小，可以想到区间DP。
设f[i][j]表示吃掉的派是[i,j]的子集的最大权值。
显然，f[i][j]=max{f[i][k-1]+f[k][j]}，k$\in$[i,j]
但这样的转移不能加入新的牛。
可以考虑待合并的两个状态f[i][k-1]和f[k+1][j],此时k这个派还没有牛动。
我们设mx[k][i][j]表示满足i<=l[k]<=k<=r[k]<=j的所有牛的最大权值。
那么加入新牛的转移方程就出炉了：
f[i][j]=max{f[i][k-1]+mx[k][i][j]+f[k+1][j]},k$\in$(i,j)
复杂度O($n^3$)
代码：
```
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
int n,m,mx[330][330][330],f[330][330],W,X,Y;
int main(){
freopen("pieaters.in","r",stdin);
freopen("pieaters.out","w",stdout);
read(n);read(m);
memset(mx,0,sizeof(mx));
F(i,1,m){
read(W);read(X);read(Y);
F(j,X,Y)mx[j][X][Y]=max(W,mx[j][X][Y]);
}
F(i,1,n){
FOR(j,i,1){
F(k,i,n){
if(j>1)mx[i][j-1][k]=max(mx[i][j-1][k],mx[i][j][k]);
if(k<n)mx[i][j][k+1]=max(mx[i][j][k+1],mx[i][j][k]);
}
}
}
FOR(i,n,1){
F(j,i,n){
F(k,i,j-1)f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
F(k,i,j)f[i][j]=max(f[i][j],mx[k][i][j]+(k>i?f[i][k-1]:0)+(k<j?f[k+1][j]:0));
}
}
printf("%d",f[1][n]);
return 0;
}
```
推荐一下我的博客：https://www.cnblogs.com/Purple-wzy/
这里有USACO12月月赛的全部12篇题解~