首页 > ACM题库 > HDU-杭电 > HDU 1176 免费馅饼-动态规划-[解题报告] C++
2013
12-03

HDU 1176 免费馅饼-动态规划-[解题报告] C++

免费馅饼

问题描述 :

都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:

为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)

输入:

输入数据有多组。每组数据的第一行为以正整数n(0<n<100000),表示有n个馅饼掉在这条小径上。在结下来的n行中,每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。

输出:

每一组输入数据对应一行输出。输出一个整数m,表示gameboy最多可能接到m个馅饼。
提示:本题的输入数据量比较大,建议用scanf读入,用cin可能会超时。

样例输入:

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

样例输出:

4

拉拉拉拉拉拉~~~~~~~dp水水~~~~~~~~~~~~

好不容易AC之后,看status,发现这题被zzuli的小盆友们集体虐过,ORZ。。。

这题开始想得有问题,没考虑中间间隔时间大的话肿么样。今晚想了想,改成按时间DP,因为当前时间的状态只和上一秒状态有关。

所以直接用上一秒相邻两个以及自己(忘了这个,WA了几次)状态更新即可。当然,开始的时候需要存下馅饼的时间,地点,如果5可以到达的话,那么更新的时候加上去即可。

虽然很水,但是还是蛮开心的~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~大笑

#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")

using namespace std;

const int MAX = 100010;
const int MAX_N = 15;
int dp[MAX_N][MAX];
int tt[MAX_N][MAX];
int main()
{
	int n,x,t;
	while( ~scanf("%d",&n) && n )
	{
		memset(dp, 0, sizeof(dp));
		memset(tt, 0, sizeof(tt));
		int max_t = 0;
		for(int i=0; i<n; i++)
		{
			scanf("%d%d",&x,&t);
			max_t = max(max_t, t);
			tt[x][t]++;
		}	
		
		int ans = 0;
		
		for(int i=1; i<=max_t; i++)
			for(int k=0; k<=10; k++)
			{
				int t = dp[k][i-1];
				if( k >= 1 ) t = max(t, dp[k-1][i-1]);
				if( k <= 9 ) t = max(t, dp[k+1][i-1]);
				
				dp[k][i] = t;
				
				if( tt[k][i] && i >= abs(k-5) )
					dp[k][i] += tt[k][i];
				
				ans = max(ans, dp[k][i]);
			}

		printf("%d\n",ans);
	}
	
return 0;
}


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge