HDU ACM 1176 免费馅饼

分析:可以采用自底向上的方法也可以采用自顶向下的方法,这里采用第二种

#include<iostream>
using namespace std;

int dp[15][100010];

int main()
{
	int i,j,maxt,t,n,x,temp;

	while(scanf("%d",&n) && n)
	{
		maxt=0;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
		{
			scanf("%d %d",&x,&t);
			dp[x+1][t]++;
			maxt=maxt>t?maxt:t;
		}
		for(i=maxt-1;i>=0;i--)
			for(j=1;j<=11;j++)
			{
				temp=dp[j+1][i+1];
				temp=temp>dp[j][i+1]?temp:dp[j][i+1];
				temp=temp>dp[j-1][i+1]?temp:dp[j-1][i+1];
				dp[j][i]=temp+dp[j][i];
			}

		printf("%d\n",dp[6][0]);
	}
	return 0;
}
时间: 04-23

HDU ACM 1176 免费馅饼的相关文章

hdu 1176 免费馅饼(数塔类型)

http://acm.hdu.edu.cn/showproblem.php?pid=1176 免费馅饼 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 33362    Accepted Submission(s): 11410 Problem Description 都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上

[2016-03-29][HDU][1176][免费馅饼]

时间:2016-03-29 09:46:34 星期二 题目编号:[2016-03-29][HDU][1176][免费馅饼] #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int maxt = 100000 + 10; int dp[maxt][11]; int a[maxt][11]; int main(){ int n,x,t,maxT; whi

HDU 1176免费馅饼 DP数塔问题转化

L - 免费馅饼 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 1176 Appoint description:  prayerhgq  (2015-07-28) System Crawler  (2015-11-21) Description 都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼.

hdu 1176 免费馅饼

免费馅饼 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 26519 Accepted Submission(s): 9032 Problem Description 都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼.说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内.

HDU 1176 免费馅饼【动态规划】

解题思路:用a[i][j]表示在第i秒在地点j的掉落馅饼的数量,设整个馅饼掉落的时间持续为timemax,即为矩阵的高度,一共0到10个地点,为矩阵的长度,如图,即可构成数塔,因为考虑到在地点0的时候,j-1为负数,所以将地点均从1开始处理则有a[i-1][j]=max(max(a[i][j],a[i][j-1]),a[i][j+1])+a[i-1][j];分别对应在每一个地点的三个选择,对应于上一秒在原地,原地左边,原地右边, 免费馅饼 Time Limit: 2000/1000 MS (Ja

Hdoj 1176 免费馅饼 【动态规划】

免费馅饼 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 26110    Accepted Submission(s): 8905 Problem Description 都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼.说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的1

hdoj 1176 免费馅饼

免费馅饼 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 28601    Accepted Submission(s): 9760 Problem Description 都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼.说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10

hdu 1176 免费馅饼 (dp)

http://acm.hdu.edu.cn/showproblem.php?pid=1176 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int dp[100000+10][12]; int mat[100000+10][12]; int main() { int n; int i,j,k; int maxt; w

hdu 1176 免费馅饼(DP)

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

HDU 1176 免费馅饼(简单DP,数塔变形)

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