走运的Zzz(动态规划)

题目连接

校oj题目,需要使用校内网打开http://172.16.163.28/JudgeOnline/showproblem?problem_id=1420

Description

程序员Zzz今天摊上了一件大好事！天上突然掉下来好多的金币，Zzz恨不得将他们全部占为己有，可是Zzz因为长期加班腰不太好弯不下腰。也就是说，Zzz只能接从天上掉下来的金币而不能弯腰捡金币。Zzz希望你能告诉他，他最多能接多少金币？
为了简化问题，我们考虑金币只在一个一维坐标轴上掉落，并且范围在0-100之间，即金币只可能落在坐标0到100之间。开始时Zzz有一初始位置，并且Zzz每秒最多可以移动一个坐标距离（当然Zzz也可以站着不动）。

Input

每组数据第一行有两个整数N(0 < N <= 1000000)、S( 0 <= S <= 100)，N表示天上将会掉下N块金币，S表示Zzz的初始位置在坐标S上。在接下来N行，每一行有两个整数t(0 < t <= 100000)，x(0 <= x <= 100)，表示t秒后有一枚金币落在坐标x上。同一秒在同一个位置可能落下多枚金币。

Output

输出Zzz能够接到的最大金币个数。

Sample Input

4 1
1 2
2 0
3 1
4 0

6 5
1 5
1 4
1 6
2 7
2 7
3 8

Sample Output

3
4

思路

和HDOJ 1176 免费馅饼差不多，只是起点位置不确定了，可以用dp[t][x]来保存在第t秒x位置上的金币个数,变形为一个数塔问题

#include 
#include 
int dp[100002][102]; // 范围如果开成dp[100002][101]会过不了 
int max(int a, int b)
{
    return (a > b ? a : b);
}
int main()
{
	int n, start, t, x, maxt;
	while(scanf("%d %d", &n, &start) != EOF)
	{
		maxt = 0;
		memset(dp, 0, sizeof(dp));		
		for(int i = 0; i < n; i++)
		{
			scanf("%d %d", &t, &x);
			if(t > maxt)
				maxt = t;
			dp[t][x]++;
		}
		for(int i = maxt - 1; i >= 0; i--)
		{
			for(int j = 0; j <= 100; j++)
			{
				dp[i][j] += max( max( dp[i+1][j], dp[i+1][j+1]), dp[i+1][j-1]); // 动态转移方程
			}
		}
		printf("%d\n", dp[0][start]);
	}	
}