题意:
有0-10一共11个位置,每个位置在每一秒可能掉落一个或者多个饼,
你只能接住当前所在位置的饼或移动到相邻位置的去接饼,
初始你站在 5 这个位置。
求最能接多少个饼。
n,表示一共掉落了n个。下面n行
p t ,表示第 t 秒在 p 位置掉落了一个饼。
分析:
其实就是数塔(hdu2084)那个题的升级版。
都是从低向上,从可能的选择中选最大的那个累加,
最后累加到顶点就是答案。
不过数塔那个题是两个选择,
而这个题是三个选择。
为了避免数组越界问题,把位置0-10转化成1-11,
同样,输入的饼的位置都要加 1 ,
初始的位置也变成了 6, 而不是 5.(WA了好多次)
代码:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e5+10;
int dp[MAXN][12];
int main()
{
int n, p, t, m;
while (scanf("%d",&n) != EOF && n)
{
m = 0;
memset(dp,0,sizeof(dp));
for (int i = 0; i < n; i++)
{
scanf("%d %d",&p, &t);
p++;
dp[t][p]++;
m = max(m, t);
}
for (int i = m-1; i >= 0; i--)
{
for (int j = 1; j <= 11; j++)
dp[i][j]+=max(dp[i+1][j], max(dp[i+1][j-1],dp[i+1][j+1]));
}
printf("%d\n", dp[0][6]);
}
return 0;
}
Comments | NOTHING