2281: 这是dp吗
[Creator : ]
Description
给出 m 个高度为 n 的柱子,每个柱子的每一单位长度上有一定的分数 ai j 表示在第 j 个柱子上的第 i 个单位长度上的分数,玩家可以选择从任意一个柱子上单位长度为 1 处开始,有以下两种操作:
(1)向上跳 1 个单位长度,高度由 i 变为 i+1,且不能跳到其他的柱子上并且得不到该位置分数;
(2)向上跳 k个单位长度,高度由 i 变为 i+k,且可以跳到任意柱子上并获得该位置上的分数
(3)当以上两种操作都无法进行时,游戏结束并结算得分。
Input
第一行包含三个整数 n,m,k 分别表示柱子的高度,数量,和跳跃的距离。
从第二行到第 n+1 行每行 m 个整数 ai j 表示第 j 根柱子上高度为 i 的分数
1≤n≤10000
1≤m≤1000
1≤k≤10000
0≤ai j≤10000
从第二行到第 n+1 行每行 m 个整数 ai j 表示第 j 根柱子上高度为 i 的分数
1≤n≤10000
1≤m≤1000
1≤k≤10000
0≤ai j≤10000
Output
一个整数表示可以取得的分数的最大值
Sample Input Copy
5 3 2
1 4 3
2 2 5
4 3 4
7 2 7
1 2 1
Sample Output Copy
11
HINT
从第2列开始,初始分数为4,向上移动一个单位长度(不获取分数)到达第2行第2列,再向上跳k=2个单位长度到达第4行第1列,或第4行第3列,总分数都是11