题解 P5851 【[USACO19DEC]Greedy Pie Eaters】

· · 题解

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篇题解~