TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3638
  • 题目
  • P3638采蘑菇
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    最近,何老板玩一款名叫“采蘑菇”的有趣手机游戏。
    游戏地图由水平放置的n块砖(编号1到n)构成,每一秒钟,每块砖上会新长出一些蘑菇,蘑菇的生命时间只有1秒钟,1秒钟后蘑菇就消失了。游戏玩家操控的游戏角色“马里奥”一开始位于第k块砖上,每一秒钟,马里奥有三种移动方式可以选择:
    1.原地不动,并采摘该砖上的蘑菇;
    2.移动到左边一块砖,并采摘该砖上的蘑菇;
    3.移动到右边一块砖,并采摘该砖上的蘑菇;
    游戏一个持续t秒钟,问马里奥最多能采集到多少颗蘑菇。

    输入格式

    第一行,四个整数n,t,k,分别表示砖块的数量,游戏的持续时间和一开始马里奥所处的位置。
    接下来一个t*n的整数矩阵,其中第i行描述第i秒钟的情况,第i行第j个数表示第i秒第j块砖上长出的蘑菇数。

    输出格式

    一行,一个整数,表示能够采摘到的最多蘑菇数。

    样例输入

    样例输入1:
    4 3 2
    3 1 1 1
    2 1 1 1
    1 5 4 1

    样例输入2:
    5 3 3
    3 1 3 3 2 
    5 6 5 1 6 
    7 4 3 4 4 

    样例输入3:
    6 4 2
    3 7 1 3 1 5 
    4 2 6 6 3 6 
    2 2 2 4 7 7 
    2 7 6 2 4 6 

    样例输出

    样例输出1:
    10

    样例输出2:
    16

    样例输出3:
    23

    提示

    对于30%的数据 1<=n<=10, 1<=t<=5;
    对于100%的数据 1<=n<=100, 1<=t<=1000 ,1<=每块砖上长出的蘑菇数<=10000

    样例1说明:
    第一秒由2号砖移动到1号砖,采3颗蘑菇
    第二秒呆在1号砖不动,采2颗蘑菇
    第三秒由1号砖移动到2号砖,采5颗蘑菇