题目链接

对于输入的每行四个数据，由于题目中说到了“当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼”，所以我们首先将从h到1消耗的时间不是v的整数倍的选项通过continue过滤掉。将那些符合题目条件的数，将其能产生的价值保存到二维数组q中，第一维表示水平位置，第二维表示时间，并通过tt记录下符合条件的最大的时间。

同时我们将f数组记为当前位置当前时间能获取的最大时间，由于初始的位置已经规定，若正着递推，需要考虑相对应时间下水平位置可能的取值，这样较为麻烦，所以我们采用倒着推，然后去选取f[(w >> 1) + 1][0]（初始位置初始状态）的最大值。

这样的话我们只需将时间从最大值tt开始向前推，水平位置从1到w遍历，f[i][j]的值等于f[i + k][j + 1]（-2 <= k <= 2） + q[i][j]中的最大值，并对每次更新通过path[i][j]记录下k（更新的位置）。

using namespace std;
int q[200][2000], f[200][2000], path[200][2000];
int main(){
    int w, h;
    cin >> w >> h;
    h -= 1;
    int a, b, c, d, tt = 0;
    while(cin >> a >> b >> c >> d){
        if(h % c)    continue;
        int t = a + h / c;
        q[b][t] += d;
        tt = max(tt, t);
    }
//     cout << tt << endl;
    for(int i = tt; i >= 0; i --){
        for(int j = 1; j <= w; j ++){
            for(int k = -2; k <= 2; k ++){
                int temp = j + k;
                if(temp < 1 || temp > w)    continue;
                if(f[j][i] < f[j + k][i + 1] + q[j][i]){
                    f[j][i] = f[j + k][i + 1] + q[j][i];
                    path[j][i] = k;
                }
            }
        }
    }
    cout << f[(w >> 1) + 1][0] << endl;
    int st = (w >> 1) + 1;
    for(int i = 0; i < tt; i ++){
        cout << path[st][i] << endl;
        st += path[st][i];
    }
}