NOI 1998 免费馅饼

附题目链接：http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4901

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte

描述

SERKOI最新推出了一种叫做“免费馅饼”的游戏:游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。
当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。

输入

输入文件的第一行是用空格隔开的两个正整数，分别给出了舞台的宽度W（1到99之间的奇数）和高度H（1到100之间的整数）。

接下来依馅饼的初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0到1000秒），水平位置、下落速度（1到100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。
输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

输出文件的第一行给出了一个正整数，表示你的程序所收集的最大分数之和。

其后的每一行依时间顺序给出了游戏者每秒的决策。输出0表示原地不动、1或2表示向右移动一步或两步、-1 或-2表示向左移动一步或两步。输出应持续到游戏者收集完他要收集的最后一块馅饼为止。

样例输入

3 3

0 1 2 5
0 2 1 3
1 2 1 3
1 3 1 4

样例输出

-1
1
1

题目来源

NOI1998

大概就是一个比较简单的dp，唯一注意两点，就是题上强调的必须在某一秒末恰好到达游戏者所在的格子中才算收集，第二就是开始时刻为0，（先题意没读准，wa了几次），也没啥其它trick。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 const int N = 101 , T = 1113 ;
 5 using namespace std ;
 6 int w,h,score[T][N] , f[T][N],times;
 7 short int nxt[T][N]; 
 8 
 9 void Init( )
10 {
11     scanf("%d%d",&w,&h);
12     int ti,wi,vi,ci;   
13     while(~scanf("%d%d%d%d",&ti,&wi,&vi,&ci))
14     {
15         if((h-1)%vi==0||ti==0)
16         {
17             int t = (h-1) / vi + ti ;
18             times = max(times,t);
19             score[t][wi] += ci ;
20         }
21         
22     }
23 }
24 
25 int dp(int ti,int wi)
26 {
27     if(ti > times ) return 0 ;
28     if(~f[ti][wi]) return f[ti][wi] ;
29     int ret = 0 ; short int net = 0 ;
30     for(int i = -2; i <= 2 ; ++i)
31     {
32         if(wi + i < 1 || wi + i > w) continue;
33         int tmp = dp(ti+1,wi+i)+score[ti+1][wi+i];
34         if(tmp>ret) ret = tmp,net = i ;
35     }
36     f[ti][wi] = ret;nxt[ti][wi] = (short int)net;
37     return ret;
38 }
39 
40 void dfs(int ti,int wi)
41 {
42     if(ti > times) return ;
43     if(!f[ti][wi]) return ;
44     printf("%d
",nxt[ti][wi]);
45     dfs(ti+1,wi+nxt[ti][wi]);
46 }
47 
48 
49 void Solve()
50 {
51     memset(f,-1,sizeof(f)) ;
52     int ans = dp(0,(w+1)>>1) ;
53     printf("%d
",ans);
54     dfs( 0 , (w+1)>>1 ) ;
55 }
56 
57 int main( )
58 {
59 //    freopen("freepizza.in","r",stdin);
60 //    freopen("freepizza.out","w",stdout);
61     Init();
62     Solve();
63     fclose(stdin);
64     fclose(stdout);
65     return 0;
66 }