1644 免費餡餅（巴蜀oj上的編號）
題面：
SERKOI最新推出了一種叫做“免費餡餅”的游戲。 游戲在一個舞台上進行。舞台的寬度為W格，天幕的高度為H格，游戲者占一格。開始時，游戲者站在舞台的正中央，手裡拿著一個托盤。 游戲開始後，從舞台天幕頂端的格子中不斷出現餡餅並垂直下落。游戲者左右移動去接餡餅。游戲者每秒可以向左或右移動一格或兩格，也可以站在願地不動。 餡餅有很多種，游戲者事先根據自己的口味，對各種餡餅依次打了分。同時在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當餡餅在某 一秒末恰好到達游戲者所在的格子中，游戲者就收集到了這塊餡餅。 寫一個程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分數之和最大。 輸入數據： 第一行:寬度W（1~99奇數）和高度H（1 ~ 100整數） 接下來給出了一塊餡餅信息。由4個正整數組成，分別表示了餡餅的初始下落時刻、水平位置、下落速度、分值。 游戲開始時刻為0。從1開始自左向右依次對水平方向的每格編號。 輸出數據： 收集到的餡餅最大分數之和。 ——————————————分割線———————————————————————————————————————————————————— 題解： 由於餡餅下落的時間和速度都不同，人只能向左右移動，餡餅只能向下移動。人和餡餅都同時移動，思考起來比較復雜，因此我們需要轉變思路： 算出每個時刻落到最底層的每個格子有多少分值的餡餅。 如果將餡餅當成參照物，則餡餅向下落，可以看成餡餅不動，人往上走去摘取餡餅，這樣人每1時刻都可以走到上一行的5個格子， 這道題是經典動規模型數塔的變形，將餡餅落下的位置看做數塔中的列數，將下落的時間看做數塔中的行數，問題轉化為求解從塔底到塔頂的最長路徑。 計算出每個格子每個時刻可能達到的餡餅分值，填入W*H的天幕表。 代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int w,h;
struct pie
{
int time,pos,speed,value,t;
}s[10001];//用結構體來記錄數據
int f[1001][1001];//記錄決策
int main()
{
cin>>w>>h;
int n=1,ss,maxn=-999,ans=0;
//while (scanf("%d%d%d%d",s[n].time,s[n].pos,s[n].speed,s[n].value)==4)
while (cin>>s[n].time>>s[n].pos>>s[n].speed>>s[n].value)//由於不知道數據個數，用while讀入
{
s[n].t=ceil(h/s[n].speed)+s[n].time;//t指該餡餅下落下來（到最後一格）的時間
n++;//這一步核心意思就是將該時間取整，但是是加一位（2.....=3）
}
n-=1;//n為餡餅個數
for (int i=1;i<=n;i++)
{
f[s[i].pos][s[i].t]+=s[i].value;
maxn=max(s[i].t,maxn);//找到最晚的餡餅的時間
}
for (int j=maxn-1;j>=0;j--)
for (int i=1;i<=w;i++)
{
if (f[i-2][j+1]&&i-2>0) ans=max(ans,f[i-2][j+1]);
if (f[i-1][j+1]&&i>1) ans=max(ans,f[i-1][j+1]);
if (f[i][j+1]) ans=max(ans,f[i][j+1]);
if (f[i+2][j+1]&&i+2<=w) ans=max(ans,f[i+2][j+1]);
if (f[i+1][j+1]&&i+1<=w) ans=max(ans,f[i+1][j+1]);
f[i][j]+=ans;//狀態轉移方程應用
}
cout<<f[w/2+1][0];//由於人以中間為起點，所以輸出（w/2+1,0)
return 0;
}
