题解 P2854 【[USACO06DEC]牛的过山车Cow Roller Coaster】

· · 题解

与背包问题类似

核心内容：

f[i][j]的意义：坐标为0~i的连续轨道中， 使用成本为j时的最大乐趣值。

状态转移方程：f[xi+wi][j+ci]=max(f[xi][j]+fi,f[xi+wi][j+ci])(1<=i<=n,0<=j<=b-ci)

注：需保证此时0~xi+wi均有轨道连着，这个技巧下面会讲到

基本步骤：

1.初始化二维数组f的值为-1(当没有可行方案时，是输出-1的，这点不知道为什么没翻译出来)并且f[0][0]=0

2.用结构体储存每根轨道的xi,wi,fi和ci

3.用sort按xi从小到大排序(方便dp)

4.dp中，当f[xi][j]不为-1时，进行状态转移，因为f[xi][j]等于-1说明没有轨道从起点一直连到xi(这就保证了0~xi+wi均有轨道连着)

5.输出f[l][i] (0<=i<=b)中的最大值

代码一波

#include<bits/stdc++.h>
using namespace std;
int l,n,b,f[1001][1001],ans=-1;
struct FT{
    int st;
    int ed;
    int f;
    int v;
};
FT p[100001];
bool cmp(FT a1,FT a2){
    return a1.st<a2.st;
}
int main(){
    scanf("%d %d %d",&l,&n,&b);
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++){
        int b;
        scanf("%d %d %d %d",&p[i].st,&b,&p[i].f,&p[i].v);
        p[i].ed=p[i].st+b;
    }
    sort(p+1,p+1+n,cmp);
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=b-p[i].v;j++){
            if(f[p[i].st][j]!=-1)f[p[i].ed][j+p[i].v]=max(f[p[i].ed][j+p[i].v],f[p[i].st][j]+p[i].f);
        }
    }
    for(int i=0;i<=b;i++)ans=max(ans,f[l][i]);
    cout<<ans;
    return 0;
}

提交记录

104ms / 5.4MB

代码：0.71KB C++