免费馅饼
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12017 Accepted Submission(s): 3997
Description都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人,所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏,虽然在游戏中是个身手敏捷的高手,但在现实中运动神经特别迟钝,每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标:
为了使问题简化,假设在接下来的一段时间里,馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼?(假设他的背包可以容纳无穷多个馅饼)
Input
输入数据有多组。每组数据的第一行为以正整数n(0<n<100000),表示有n个馅饼掉在这条小径上。在结下来的n行中,每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
Output
每一组输入数据对应一行输出。输出一个整数m,表示gameboy最多可能接到m个馅饼。
提示:本题的输入数据量比较大,建议用scanf读入,用cin可能会超时。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4
Source
HDU1176
设a[i][j]为第i秒的j位置掉下的馅饼数量,f[i][j]为第i秒在j位置接馅饼最多可以接到的最多馅饼数量。由于每秒只能移动一个位置,因此这一状态可能由三种情况达到:
- f[i - 1][j - 1]
- f[i - 1][j]
- f[i - 1][j + 1]
这三种情况中的最大值加上当前位置可以接到的馅饼数即是当前位置可以接到的最大馅饼数量:-
f[i][j]=max(f[i-1][j-1],f[i-1][j],f[i-1][j+1])+a[i][j];
可以看出,当前状态与之前同一阶段的多个状态有关,而类似于Ugly
Numbers等动态规划中的每一阶段都只有一个状态,为区分两者,我将它称为二维动态规划。当然,这道题只是二维动态规划中最简单的一种罢了。
但需要注意的是下面这种情况:
-
#include<iostream>
-
#include<algorithm>
-
usingnamespacestd;
-
inta[12][100002];
-
intf[12][100002];
-
intmain(){
-
intn;
-
while(scanf("%d",&n)!=EOF&&n){
-
memset(a,0,sizeof(a));
-
memset(f,0,sizeof(f));
-
intx,T,i,j,maxT=0,ans=0;
-
while(n--){
-
scanf("%d%d",&x,&T);
-
++a[x][T];
-
maxT=max(maxT,T);
-
}
-
for(i=0;i<11;++i){
-
for(j=1;j<=maxT;++j){
-
if(j==1&&(i<4||i>6)){
-
continue;
-
}
-
f[i][j]=f[i][j-1];
-
f[i][j]=max(f[i][j],f[i-1][j-1]);
-
f[i][j]=max(f[i][j],f[i+1][j-1]);
-
f[i][j]+=a[i][j];
-
}
-
}
-
for(i=0;i<11;++i)
-
ans=max(ans,f[i][maxT]);
-
printf("%d\n",ans);
-
}
-
return0;
- }
这段代码看似没错,但必然是Wrong Answer,因为阶段划分错误,即将位置作为了阶段,先算出一个位置所有时间的状态,再计算下一位置所有时间的状态,但实际上状态与上一时间的下一位置有关,而该值却尚未算出,因此运行结果必然是错误的。
二维动态规划阶段的划分应该正确地选择,这也是与一维动态规划的一点区别之处吧。
正确代码如下:
-
#include<iostream>
-
#include<algorithm>
-
usingnamespacestd;
-
inta[100001][12];
-
intf[100001][12];
-
intmain(){
-
intn;
-
while(scanf("%d",&n)!=EOF&&n){
-
memset(a,0,sizeof(a));
-
memset(f,0,sizeof(f));
-
intx,T,i,j,maxT=0,ans=0;
-
while(n--){
-
scanf("%d%d",&x,&T);
-
++a[T][x];
-
maxT=max(maxT,T);
-
}
-
f[1][4]=a[1][4];
-
f[1][5]=a[1][5];
-
f[1][6]=a[1][6];
-
for(i=2;i<=maxT;++i){
-
for(j=0;j<11;++j){
-
f[i][j]=f[i-1][j];
-
if(j>0)
-
f[i][j]=max(f[i][j],f[i-1][j-1]);
-
if(j<10)
-
f[i][j]=max(f[i][j],f[i-1][j+1]);
-
f[i][j]+=a[i][j];
-
//printf("%d ", f[i][j]);
-
}
-
//printf("\n");
-
}
-
for(i=0;i<11;++i)
-
ans=max(ans,f[maxT][i]);
-
printf("%d\n",ans);
-
}
-
return0;
- }
=======================签 名 档=======================
原文地址(我的博客):http://www.clanfei.com/2012/04/646.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
杭电hdu acm资料所用杭电的acm题
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
写一个数据结构算法,杭电上一道题目,有关数据结构的题目。
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?...
此程序为hdu的acm2010题,就是解决水仙花数问题
acm经典题、结题报告,对初学者非常用用,我就从中学到了很多东西
ACM比赛解题报告,包括hdu1880、zoj1010、zoj1015,为原创的报告,算法不一定最优的
杭电acm解题报告 详细解析2000-2099 适合acm初学者
杭电acm 一些java语言实现的水题目
杭电的一些acm题目,都是我自己一个一个自己提交的
ACM_算法模板集史上最完整收藏版223页全免费版.pd
HDU_ACM_1002_大数相加C源代码,利用字符串处理
背包九讲2.0_算法_动态规划_ACM_
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
ACM_HDU 我的 acm 问题的一部分在 hdoj 中解决了。
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
ACM HDU题目分类,我自己总结的大概只有十来个吧
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
noi试题和解析,对于参加acm非常有帮助