免费馅饼(牛客刷dp）
免费馅饼
- 比赛主页
- 我的提交
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
SERKOI最新推出了一种叫做“免费馅饼”的游戏:游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。
游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。
当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。
输入描述:
第一行是用空格隔开的两个正整数，分别给出了舞台的宽度W（1到99之间的奇数）和高度H（1到100之间的整数）。 接下来依馅饼的初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0到1000秒），水平位置、下落速度（1到100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。 输入文件中同一行相邻两项之间用一个或多个空格隔开
输出描述:
第一行给出了一个正整数，表示你的程序所收集的最大分数之和。 其后的每一行依时间顺序给出了游戏者每秒的决策。输出0表示原地不动、1或2表示向右移动一步或两步、-1 或-2表示向左移动一步或两步。输出应持续到游戏者收集完他要收集的最后一块馅饼为止
示例1
输入
复制
3 3 0 1 2 5 0 2 1 3 1 2 1 3 1 3 1 4
输出
复制
12 -1 1 1
当馅饼在某一秒末恰好到达游戏者所在的格子中，代表的是馅饼在整数秒的时候必须掉落在游戏者所在的格子的顶端
这道题的状态转移方程还是很好求的
dp[i][j]=dp[i+1][j+k]+a[i][j];
由于我们知道了游戏者开始是从哪里开始的，但是我们并不清楚最终的状态，所以我们可以从后向前枚举，代码如下：
对于我们的路径我们只需要通过倒叙求最优解的时候记录一下，最后正着输出出来
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1100][110];
int dp[1100][110];
int path[1100][110];
signed main()
{int w,h;cin>>w>>h;h--;int maxt=-1;int t,wei,v,value; while(cin>>t>>wei>>v>>value){if(h%v!=0)continue;a[t+h/v][wei]+=value;maxt=max(maxt,t+h/v);}for(int i=maxt;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(dp[i][j]<dp[i+1][j+k]+a[i][j]){dp[i][j]=dp[i+1][j+k]+a[i][j];path[i][j]=k;}}}}cout<<dp[0][(w>>1)+1]<<endl;int ss=(w>>1)+1;for(int i=0;i<maxt;i++){cout<<path[i][ss]<<endl;ss+=path[i][ss];}} 
