P2795 Facer爱游泳

    • 2通过
    • 37提交
  • 题目提供者 _Sugar_
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 搜索 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Facer爱游泳哎

    他在一个N*M的游泳池里(1<=N<=100,1<=M<=1000)

    游泳池的每个格子有可能有变速器或者钱(只能有一种)Facer经过一个格子,如果是钱,就可以拿到(有可能是负数) 如果是变速器,那么就会受到变速器的影响

    Facer要从(1,1)去(1,M)

    Facer的行动规则:

    Facer有两个方向的速度,水平和垂直,水平速度恒定为1(以下速度指垂直速度)

    若Facer的速度是v,那么他现在位于(x,y),将会达到(x+v,y+1)(若x+v>n,到达(n,y+1),若x+v<1,到达(1,y+1))

    Facer的行动:

    到了每一个格子,Facer可以选择将自己的速度+1,-1或者不变(依然受变速器影响)

    变速器:

    如果变速器的变速效果是u,当前速度是v,下一秒Facer到达的格子为(x+u+v,y+1)或(x+u+v+1,y+1)或(x+u+v-1,y+1)

    ATTENTION:

    Facer的速度会维持,但是有一个例外。

    当Facer到达水面,即位于(1,k)时,Facer的速度会变成0(当然他仍然可以选择将速度+1)

    Facer不能长时间在水下,他必须k(k<=10)秒浮出水面一下

    Facer想从(1,1)到(1,M)的路途中获得最多的钱

    输入输出格式

    输入格式:

    第一行N M k

    接下来N行M列

    每个格子用一个字母和数字(有可能无)表示

    钱: s钱数量

    变速器: v变速量

    输出格式:

    最多的钱数

    输入输出样例

    输入样例#1: 复制
    3 3 3
    s1 v1 s1
    s3 s19 v2
    v3 s-1 v-1
    输出样例#1: 复制
    2

    说明

    10% 1<= N,M <= 5

    40% 1 <= N,M <= 100

    100% 1 <= N <= 100 , 1 <= M <= 1000 , 1 <= k <= 10 , -1000 <= 钱 <= 1000

    -20 <= 变速器 <= 20

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