P3257 [JLOI2014]天天酷跑

    • 55通过
    • 233提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 搜索 记忆化搜索 2014 吉林 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在游戏天天酷跑中,最爽的应该是超级奖励模式了吧,没有一切障碍,可以尽情的吃金币,现在请你控制游戏角色来获得尽可能多的分数。游戏界面离散为一个长度为1~n,高度为1~m(初始点为(0,1))的矩阵图。每个格子上都有收益(-1~1000),-1表示该点不能通过。游戏角色从起点一路奔跑向终点,中途可以跳跃来获得更高的分数,在空中还能进行连跳。

    游戏开始前你可以设定跳跃的高度,以及能连跳的次数,初始跳跃高度为1,连跳数为1(最多为5),升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定,连跳必须在下落过程中可以使用。所有操作都将在整点上完成,需要保证设定完的跳跃高度及连跳数,无法跳出游戏高度上限。

    从(1,1)点用一次跳跃,一次经过(2,2),(3,3),(4,2),(5,1)。

    以下是连跳数为2连跳,跳跃高度为2的跳跃方案:

    从(1,1)起跳,依次经过(2,2),(3,3),(4,2)再使用连跳,经过(5,3),(6,4),(7,3),(8,2),(9,1)。

    输入输出格式

    输入格式:

    第一行四个整数n,m,cost1,cost2。n,m如题意所示,cost1,cost2分别表示每升一级跳跃高度,连跳数所需的花费。

    接下来m行,每行n个数。第i行第j个数表示地图中高度为i,长度在第j列处的收益。

    输出格式:

    如果无法跑出终点线,就输出”mission failed“,否则输出一行三个数,分别表示最大收益;及最大收益时,最小的连跳数;最大收益,最小连跳数时,最小的跳跃高度。

    输入输出样例

    输入样例#1: 复制
    7 4 6 10
    9 4 7 7 4 3 2
    18 8 9 4 15 12 4
    19 2 4 7 10 18 12
    8 1 13 14 16 0 14
    输出样例#1: 复制
    67 1 2

    说明

    提示

    20%数据满足 m=2, n<=100000;

    另有80%数据 n<=10000,2<m<=20,其中20%数据 2<n<=10,m<=10;

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。