题解 | #免费馅饼#

思路：dp

开一个dp[i][j]数组，其中i代表位置,j代表时间

然后在馅饼恰好收集到的时候dp[pos][t]+=val(pos代表馅饼位置,t代表下落到的时间,val代表馅饼价值)

之后我们按时间从后往前枚举位置与操作即可

为什么不从前往后枚举？

因为你一开始的位置你是知道是dp[w/2+1][0]的

如果往后枚举那么就不知道最大的价值在哪个位置，就不好弄方案

往前枚举就让dp[w/2+1][0]这时候拥有的价值最大

再另外开个la[i][j]数组保存方案即可

具体见代码注释

AC代码：

#define long long int
using namespace std;
int dp[150][1350];//i表示位置,j表示时间
int la[150][1350];
int dx[]= {-2,-1,0,1,2};
signed main()
{
    int w,h;
    cin>>w>>h;
    int a,b,c,d;
    int mmax=0;
    while(cin>>a>>b>>c>>d)
    {
        if((h-1)%c)continue;
        int t=a+(h-1)/c;
        mmax=max(t,mmax);
        dp[b][t]+=d;
    }
    for(int i=mmax-1; i>=0; i--)
    {
        for(int j=1; j<=w; j++)
        {
            int ma=0,p=0;
            for(int k=0; k<5; k++)//模拟移动操作，找下一秒能到达的最大价值点
            {
                int pos=j+dx[k];
                if(pos>w||pos<1)continue;
                if(dp[pos][i+1]>ma)
                {
                    ma=dp[pos][i+1];
                    p=dx[k];
                }
            }
            la[j][i]=p;//记录方案
            dp[j][i]+=ma;
        }
    }
    int pos=w/2+1,t=0;
    cout<<dp[pos][0]<<endl;
    while(dp[pos][t])
    {
        int x=la[pos][t];
        pos+=x,t++;//之后位置跟时间都变了
        if(dp[pos][t])cout<<x<<endl;
    }
    return 0;
}