hdu1176-免费馅饼(动态规划)

发布于 2019-08-08  538 次阅读


问题传送门:

题意:

有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;
}

Simple And Clear