免费馅饼题解

免费陷阱

题目描述

SERKOI最新推出了一种叫做“免费馅饼”的游戏:游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。 馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。 当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。 写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。

分析

一开始我看到这个题毫无头绪，不知道从哪里下手，因为感觉题目给的信息太多了，不知道怎么用，但是静下心来想就会发现，题目给的有效信息其实只有两个，即馅饼刚好下落的时刻和下落的水平位置。其中馅饼刚好下落的时刻是需要我们根据馅饼下落时间、速度和天幕高度H来计算的。那么我们就根据这两个有效信息来解题。

状态表示

f[i][j]表示在i时刻时，游戏者在j位置所获得的最大分值。

状态计算

f[i][j] = max(f[i + 1][j + k] + s[i][j],f[i][j]) 注意：这里要从i + 1时刻转移到i时刻，因为题目中的初始位置是在mid位置（即舞台中央），这样倒过来推，最后的最大分值就是f[0][mid]。

下面是我的ac代码

using namespace std;
int w,h,s[11100][1100],f[11100][1100];//数组s[i][j]表示在i时刻调到j位置的馅饼的分值
int path[11100][1100];

//游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动
//怎么记录每一步状态？？？？

int main()
{
    cin >> w >> h;
    h -= 1;
    int start,pos,v,score,t,maxt = 0;
    while(scanf("%d %d %d %d", &start, &pos, &v, &score) != EOF){
        if(h % v) continue;//一定要刚好在整数时刻下落游戏者才有可能接到
        t = start + h / v;
        if(t > maxt) maxt = t;
        s[t][pos] += score;//同一时刻可能有多个馅饼同时掉落
    }
    int mid = (w + 1) / 2;
    f[0][mid] = 0;//0时刻在中间位置
    for(int i = maxt;i >= 0;i --){
        for(int j = 1;j <= w;j ++){
            for(int k = -2;k <= 2;k ++){
                if(j + k >= 1 && j + k <= w){
                    if(f[i][j] < f[i + 1][j + k] + s[i][j]){////注意这里不要漏掉了不移动的状态，即在这一时刻游戏者可能不移动，k = 0
                        f[i][j] = f[i + 1][j + k] + s[i][j];
                        path[i][j] = k;//记录每一步的移动
                    }
                }
            }
        }
    }
    int x = mid;
    cout << f[0][mid] << '\n';
    for(int i = 0;i < maxt;i ++){
        cout << path[i][x] << '\n';
        x += path[i][x];
    }
    return 0;
}

看到这里大家可能对我的代码有一些疑问

问：为什么h要减一？

答：仔细观察题目我们可以发现，题目说“游戏者占一格”，并且图中游戏者的高度也占了一格，所以当馅饼下落到高度为1的位置可以被接住