题解 | #免费馅饼#

#include<iostream>
using namespace std;
using ll=long long;
//没必要考虑馅饼的运动，我们只关心馅饼“何时”到达底部。
//只有在某一秒末正好到达的馅饼，才会计数
//以时间为轴进行动态规划，已知起点，未知终点
//故从后往前递推（为何？因为“发散or收敛”？）
//从后往前推并不会影响结果的正确性（为何？）
int dp[105][1500];//位置和到达时间
int path[105][1500];//记录路径
int dx[5]={-2,-1,0,1,2};
int main()
{
    int m,h;
    cin>>m>>h;
    int a,b,c,d;
    int maxt=0;
    while(cin>>a>>b>>c>>d)
    {
        if((h-1)%c!=0)//不能正好到达
            continue;
        int t=(h-1)/c+a;//到达时刻=起始时刻+掉落时间
        dp[b][t]+=d;
        maxt=max(t,maxt);
    }
    for(int i=maxt;i>=0;--i)//枚举时间
    {
        for(int j=1;j<=m;++j)//枚举位置
        {
            int maxdp=0;
            int index=0;
               for(int k=0;k<5;++k)
               {
                   int tp=(j+dx[k]);
                   
                   if(tp<1||tp>m)
                       continue;
                   //试图“tp<=0?1:tp” ，是错误的！哪怕当前点在左边界无法转移
                                             //也会被认定为和当前位置相同的分值
                   if(dp[tp][i+1]>maxdp)//找到最优子解
                   {
                       maxdp=dp[tp][i+1];
                       index=tp;//记录从哪里转移过来
                   }
               }
            dp[j][i]+=maxdp;
            path[j][i]=index;//path中保存上一秒所在的位置，如果他自己就是端点，那么值就为0
        }
    }
     
    int t=0;
    cout<<dp[(m+1)/2][t]<<endl;
    /*
    while(dp[pos][t])
    {
        int x=path[pos][t];
        pos+=x;
        t++;
        if(dp[pos][t])
            cout<<x<<endl;
    }
    */
   int pos=(m+1)/2;
    for(int i=0;i<=maxt;++i)//从起点回溯
    {
    
        int tt=path[pos][i];
        if(tt==0)
            break;
        cout<<tt-pos<<endl;
        pos=tt;
    }
    
}