题意

• 在一个W*H的长方形平面内，有若干块饼下坠，每块饼会有{下坠时间，下坠位置，下坠速度，价值}四个信息
• 人最初站在中间，可以移动(-2,-1,0,1,2)，请输出最多获得的价值以及开始后每一秒的操作

思路

• 这题有很多坑点
• 显然是一个动态规划，状态转移方程
• 坑点1:由于起点强制锁定在中间，但从中间开始发散着dp不好描述，又从第一秒开始往后接饼和从最后一秒往前接饼效果是一样的，所以不妨从最后一秒开始倒推dp过程，即规划的过程从i=maxt到i=0
• 坑点2:计算时间的时候，虽然高度是H但是只用下落(H-1)的高度，所以下落时间是
• 坑点3:题干中描述，只有在每一秒末落下的饼才会被接到，也就是只有下落时间是整数的才会被考虑，那么if((H-1)%v) continue;
• 坑点4:题干没描述，但是当值是相同的时候要尽可能往左走

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
/**
 * dp[i][j]表示倒数第i秒在j位置能获得的最大得分
 */
const int N=1e6+10;
int dp[N][120];
int val[N][120];
int path [N][120];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int W,H;
    cin >> W >> H ;
    int st,x,v,sco;
    int mxt=0;
    while(cin >> st >> x >> v >> sco){
        if((H-1)%v) continue;
        int t=st+(H-1)/v;
        val[t][x]+=sco;
        mxt=max(mxt,t);
    }

    for(int i=mxt;i>=0;i--){
        for(int j=1;j<=W;j++){
            if(j>2&&dp[i+1][j-2]+val[i][j]>dp[i][j]){
                dp[i][j]=dp[i+1][j-2]+val[i][j];
                path[i][j]=-2;
            }            
            if(j>1&&dp[i+1][j-1]+val[i][j]>dp[i][j]){
                dp[i][j]=dp[i+1][j-1]+val[i][j];
                path[i][j]=-1;
            }
            if(dp[i+1][j]+val[i][j]>dp[i][j]){
                dp[i][j]=dp[i+1][j]+val[i][j];
                path[i][j]=0;
            }

            if(j<W&&dp[i+1][j+1]+val[i][j]>dp[i][j]){
                dp[i][j]=dp[i+1][j+1]+val[i][j];
                path[i][j]=1;
            }
            if(j<W-1&&dp[i+1][j+2]+val[i][j]>dp[i][j]){
                dp[i][j]=dp[i+1][j+2]+val[i][j];
                path[i][j]=2;
            }                                    
        }
    }    
    cout << dp[0][(W+1)/2] << endl;
    int depth=0,start=(W+1)/2;
    while(depth<mxt){
        cout << path[depth][start] << endl;
        start+=path[depth][start];
        depth++;
    }
    return 0;
}