#P3628. [JLOI2014]天天酷跑
[JLOI2014]天天酷跑
[JLOI2014] 天天酷跑
题目描述
在游戏天天酷跑中,最爽的应该是超级奖励模式了吧,没有一切障碍,可以尽情的吃金币,现在请你控制游戏角色来获得尽可能多的分数。游戏界面离散为一个长度为1~n,高度为1~m(初始点为(0,1))的矩阵图。每个格子上都有收益(-1~1000),-1表示该点不能通过。游戏角色从起点一路奔跑向终点,中途可以跳跃来获得更高的分数,在空中还能进行连跳。
游戏开始前你可以设定跳跃的高度,以及能连跳的次数,初始跳跃高度为1,连跳数为1(最多为5),升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定,连跳必须在下落过程中可以使用。角色每走一步向右一格,地面平跑时高度不变,腾空时每一步升高或降低一格。每轮连续跳跃次数包括离地时的第一跳。到达一次跳跃的最高点后,已可开始下一次连跳。所有操作都将在整点上完成,需要保证设定完的跳跃高度及连跳数,无法跳出游戏高度上限。

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

从 起跳,依次经过 、、,再连跳,经过 、、、、。第三幅图展示从同一位置进行一次高度为 的跳跃。

输入格式
第一行四个整数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;