题解 | #免费馅饼#

一、思考状态转移方程如何写

1、原问题和子问题：

原问题：一个人可以左右移动去接饼，当游戏结束时，接到的饼的最大价值。

子问题：一个人可以左右移动，当到达某一时刻时，接到的饼的最大价值。

可见子问题的求解方式与原问题相同。

2、使子问题是最优解

显然是比较每一个由相同状态转移来的状态，得到最优解就是子问题的最优解。

3、是否无后效性：

解决后效性的最好方法就是增加维度，能把物体的每一个状态的所有要素表现清楚，这题由于子问题求解只需要人的位置和游戏时间，那么维度就是二，要素是位置和时间。

现在就得到了状态转移方程：

sc[i][j]=max(sc[i][j],sc[i+1][j+k]+have[i][j]);

二、需要注意细节：

题目中说当饼在某一秒结束时到达人所在的位置即可，也就是说，饼下落到地面的时间必须是整数。

三、路径打出：

1、循环方法

2、递归方法

#include<bits/stdc++.h>
using namespace std;
int w,h;
const int M=105;
int have[M][M];
int sc[M][M];
int path[M][M];
int mov[4]={1,-1,2,-2};
int main(){
    cin>>w>>h;
    h--;
    int tim,x,v,s;
    int maxn=-1;
    while(cin>>tim>>x>>v>>s){
        if(h%v!=0) continue;
        have[tim+h/v][x]+=s;
        maxn=max(maxn,tim+h/v);
        
    }
    for(int i=maxn;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(sc[i][j]<sc[i+1][j+k]+have[i][j]){
                        sc[i][j]=sc[i+1][j+k]+have[i][j];
                        path[i][j]=k;
                    }
                }
            }
        }
    }
    cout<<sc[0][(w>>1)+1]<<endl; 
    int pos=(w>>1)+1;
    for(int i=0;i<maxn;i++){
        cout<<path[i][pos]<<endl;
        pos+=path[i][pos];
        
    }
    return 0;
}