yy1158047452
我像风一样自由~
采纳率35.7%
2020-04-01 10:55

dp题,求大佬指点迷津,有币日后定补上

已采纳

巧接人参果
时间限制: 1 Sec 内存限制: 128 MB
提交: 270 解决: 61
[提交] [状态] [讨论版] [命题人:admin]
题目描述
唐僧率领徒弟孙悟空、猪八戒、沙和尚去西天取经,路经万寿山五庄观。 观主镇元大仙上天听道去了,临行嘱咐童子,大唐高僧路经此地,可取人参果好生款待。这人参果乃仙家之宝 ,食之能长生不老。师徒一行来到五庄观,观中童儿只将人参果款待唐僧 。悟空不甘受此冷落,加之贪吃的八戒在旁怂恿,便潜入果园偷吃人参仙果。 恰巧你也在那,于是你有缘与孙悟空一起摘人参果。不过这人参果遇金则落,遇土则遁。为此,孙悟空、猪八戒、沙和尚三人爬上果树用金箍棒等将人参果打落,而你则在树底下接人参果。 这人参果别处都不掉,就掉落在他身旁的10米范围内。人身果如果掉在了地上就不见了。当然你很聪明,可是看到这么多人身果,动作也变迟钝了,每秒种只有在移动不超过一米的范围内接住坠落的人身果。现在给你接人参果如图标上坐标: 为了使问题简化,假设在接下来的一段时间里,人参果都掉落在0-10这11个位置。开始时你站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问你最多可能接到多少个人参果?(假设背包可以容纳无穷多个人参果)

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

输出
每一组输入数据对应一行输出。输出一个整数m,表示你最多可能接到m个人参果。

样例输入
6
5 1
4 1
6 1
7 2
7 2
8 3
0

样例输出
4

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • qq_45721778 山海皆可平q 1年前

    这个题把他简化一下就是一个变形的数塔
    数塔的每行就是时间,每列就是人参果掉下的位置的坐标
    所以我们要设置一个二维数组,用一个变量记录时间的最大值,来进行循环

    图片说明

    这个是样例的输入数据,我在上面标上了行和列
    我在上面画了两条竖线,这样就更像数塔了,这两条线代表在他们外面的人参果是接不到的,那么我们要做的就是找出一条路径使得所有数字之和最大,那么不就是我们的数塔问题么?
    那么dp[0][5]就一定是接到最多人参果的地方,同时我们使用逆序也会使问题更方便,顺序的话,还要再加上一个二维数组去保存数据和

    具体代码你可以看一下这个文章
    文章

    点赞 评论 复制链接分享