P3800 Power收集

    • 450通过
    • 1.4K提交
  • 题目提供者 orangebird
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 单调队列 洛谷原创 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    据说在红雾异变时,博丽灵梦单身前往红魔馆,用十分强硬的手段将事件解决了。

    然而当时灵梦在Power达到MAX之前,不具有“上线收点”的能力,所以她想要知道她能收集多少P点,然而这个问题她答不上来,于是她找到了学OI的你。

    题目描述

    可以把游戏界面理解成一个N行M列的棋盘,有K个格子上有P点,其价值为val(i,j)

    初始灵梦可以选择在第一行的任意一个格子出发,每秒她必须下移一格。

    灵梦具有一个左右移动的速度T,可以使她每秒向左或右移动至多T格,也可以不移动,并且不能折返。移动可视为瞬间完成,不经过路途上的点,只能获得目标格子的P点。

    求最终她能获得的POWER值最大是多少?

    输入输出格式

    输入格式:

    第一行四个数字,N,M,K,T

    接下来K行每行3个数字x,y,v,代表第x行第y列有一个val为v的P点,数据保证一个格子上最多只有1个P点。

    输出格式:

    一个数字

    输入输出样例

    输入样例#1: 复制
    3 3 4 1
    1 1 3
    1 2 1
    2 2 3
    3 3 3
    
    输出样例#1: 复制
    9

    说明

    对于40%的测试点,1<=N,M,T,K<=200

    对于100%的测试点,1<=N,M,T,K<=4000

    v<=100,N,M,K,T均为整数

    by-szc

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