题目大意:
都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:
![](http://acm.hdu.edu.cn/data/images/1176_1.jpg)
为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)
解题思路:1)由题目可以知道,在某个时间点在某点接住馅饼,则前一个时间点必须在这个点的左边,右边或者就在这个点。
2)根据题设,我们不妨设dp[i][j]为在第i秒在j处接住的馅饼。
则有: dp[i][j]=Max{dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]}+a[i][j];
代码
1
#include <iostream>
2
#include <cstdio>
3
#include <cmath>
4
#include <algorithm>
5
#include <cstring>
6![](/Images/OutliningIndicators/None.gif)
7
using namespace std;
8![](/Images/OutliningIndicators/None.gif)
9
int a[100010][15];
10
int dp[100010][15];
11
int t,n,p,q,maxx;
12![](/Images/OutliningIndicators/None.gif)
13
int main()
14![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
15
while (~scanf("%d",&n))
16![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
if (n==0) break;
18
t=-(1<<30);
19
memset(a,0,sizeof(a));
20
memset(dp,0,sizeof(dp));
21
for (int i=1; i<=n; i++)
22![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
23
cin >> p >> q;
24
a[q][p]++;
25
if (t<q) t=q;
26
}
27
dp[1][5]=a[1][5];
28
dp[1][6]=a[1][6];
29
dp[1][4]=a[1][4];
30
for (int i=1; i<=t-1; i++)
31![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
32
for (int j=0; j<=10; j++)
33![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
34
if (dp[i+1][j+1]<a[i+1][j+1]+dp[i][j] && j<10)
35
dp[i+1][j+1]=dp[i][j]+a[i+1][j+1];
36
if (dp[i+1][j]<a[i+1][j]+dp[i][j])
37
dp[i+1][j]=dp[i][j]+a[i+1][j];
38
if (dp[i+1][j-1]<a[i+1][j-1]+dp[i][j] && j>0)
39
dp[i+1][j-1]=dp[i][j]+a[i+1][j-1];
40
}
41
}
42
maxx=-(1<<30);
43
for (int i=1; i<=11; i++)
44
if (dp[t][i]>maxx) maxx=dp[t][i];
45
cout << maxx << endl;
46
}
47
return 0;
48
}
49![](/Images/OutliningIndicators/None.gif)
: