hdu 1176 免费馅饼(二维dp)
免费馅饼
**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 29065 Accepted Submission(s): 9921
**
Problem Description
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）
Input
输入数据有多组。每组数据的第一行为以正整数n(0
Output
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4
Author
lwg
二维dp
状态转移方程也很容易想到
dp[i][j]表示在时间i，位置J的时候能得到的馅饼的个数。
dp[i][j]是由dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]得到。
注意边界和初始化。
因为一开始是在位置5
所以 dp[1][4]=a[1][4];
dp[1][5]=a[1][5];
dp[1][6]=a[1][6];
但是取出最大的dp[i][j]的时候出了问题导致我一直WA，而且还没有想的很明白。。
AC代码：
1
2
3 /* ***********************************************
4 Author :111qqz
5 Created Time :2016年02月22日 星期一 23时18分21秒
6 File Name :code/hdu/1176.cpp
7 ************************************************ */
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstring>
12 #include <cstdio>
13 #include <cmath>
14
15 using namespace std;
16
17 int n,t,x,maxtime;
18 long long ans;
19 const int N=1E5+7;
20 int a[N][15],dp[N][15];
21
22 int MAX(int a,int b,int c)
23 {
24 int res = -1;
25 if ( a>res )
26 res = a;
27 if ( b>res )
28 res = b;
29 if ( c>res )
30 res = c;
31 return res;
32 }
33
34 int main()
35 {
36 while ( scanf("%d",&n)!=EOF&&n )
37 {
38 ans = -1 ;
39 maxtime = -1;
40 memset(a,0,sizeof(a));
41 memset(dp,0,sizeof(dp));
42 for ( int i = 1 ; i <= n ; i++ )
43 {
44 scanf("%d %d",&x,&t);
45 a[t][x]++;
46 if ( t>maxtime )
47 maxtime = t;
48 }
49 dp[1][4] = a[1][4];
50 dp[1][5] = a[1][5];
51 dp[1][6] = a[1][6];
52 for ( int i = 2 ; i <= maxtime ; i++ )
53 for ( int j = 0 ; j <= 10 ; j++ )
54 {
55 if ( j==0 )
56 dp[i][j] = max(dp[i-1][j],dp[i-1][j+1]) + a[i][j];
57 else if ( j==10 )
58 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + a[i][j];
59 else dp[i][j] = MAX(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+a[i][j];
60 // if ( dp[i][j]>ans )
61 // ans = dp[i][j];
62
63 }
64 for ( int i = 0 ; i <= 10 ; i++)
65 if ( dp[maxtime][i]>ans )
66 ans = dp[maxtime][i];
67 printf("%I64d\n",ans);
68
69 }
70 return 0;
71 }
72
WA代码：
1
2
3 #include <iostream>
4 #include <algorithm>
5 #include <cstring>
6 #include <cstdio>
7 #include <cmath>
8
9 using namespace std;
10
11 int n,t,x,maxtime;
12 long long ans;
13 const int N=1E5+7;
14 int a[N][15],dp[N][15];
15
16 int MAX(int a,int b,int c)
17 {
18 int res = -1;
19 if ( a>res )
20 res = a;
21 if ( b>res )
22 res = b;
23 if ( c>res )
24 res = c;
25 return res;
26 }
27
28 int main()
29 {
30 while ( scanf("%d",&n)!=EOF&&n )
31 {
32 ans = -1 ;
33 maxtime = -1;
34 memset(a,0,sizeof(a));
35 memset(dp,0,sizeof(dp));
36 for ( int i = 1 ; i <= n ; i++ )
37 {
38 scanf("%d %d",&x,&t);
39 a[t][x]++;
40 if ( t>maxtime )
41 maxtime = t;
42 }
43 dp[1][4] = a[1][4];
44 dp[1][5] = a[1][5];
45 dp[1][6] = a[1][6];
46 for ( int i = 2 ; i <= maxtime ; i++ )
47 for ( int j = 0 ; j <= 10 ; j++ )
48 {
49 if ( j==0 )
50 dp[i][j] = max(dp[i-1][j],dp[i-1][j+1]) + a[i][j];
51 else if ( j==10 )
52 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + a[i][j];
53 else dp[i][j] = MAX(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+a[i][j];
54 if ( dp[i][j]>ans )
55 ans = dp[i][j];
56
57 }
58 // for ( int i = 0 ; i <= 10 ; i++)
59 // if ( dp[maxtime][i]>ans )
60 // ans = dp[maxtime][i];
61 printf("%I64d\n",ans);
62
63 }
64 return 0;
65 }
66