#P3628. [JLOI2014]天天酷跑

    ID: 2823 传统题 2000ms 128MiB 尝试: 176 已通过: 66 难度: 6 上传者: 标签>难度分类提高枚举与搜索暴力枚举动态规划线性 DP滚动数组CF1900

[JLOI2014]天天酷跑

[JLOI2014] 天天酷跑

题目描述

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

游戏开始前你可以设定跳跃的高度,以及能连跳的次数,初始跳跃高度为1,连跳数为1(最多为5),升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定,连跳必须在下落过程中可以使用。角色每走一步向右一格,地面平跑时高度不变,腾空时每一步升高或降低一格。每轮连续跳跃次数包括离地时的第一跳。到达一次跳跃的最高点后,已可开始下一次连跳。所有操作都将在整点上完成,需要保证设定完的跳跃高度及连跳数,无法跳出游戏高度上限。

一次高度为 2 的跳跃

跳跃高度为 22 时,从 (1,1)(1,1) 起跳依次经过 (2,2)(2,2)、(3,3)(3,3)、(4,2)(4,2)、(5,1)(5,1)。

跳跃高度为 22、可连续跳 22 次时,可以采用第二幅图中的方案。

下落后在半空中连跳

从 (1,1)(1,1) 起跳,依次经过 (2,2)(2,2)、(3,3)(3,3)、(4,2)(4,2),再连跳,经过 (5,3)(5,3)、(6,4)(6,4)、(7,3)(7,3)、(8,2)(8,2)、(9,1)(9,1)。第三幅图展示从同一位置进行一次高度为 44 的跳跃。

一次高度为 4 的跳跃

输入格式

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

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

输出格式

若无法通过整张地图,则输出一行 mission failed。否则输出三个整数,依次为最大净收益、取得该收益的最小连跳数,以及这两个值都相同时的最小跳跃高度。净收益是沿途各格的收益之和扣去赛前的两项升级花费。

样例 #1

样例输入 #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;