P2760 科技庄园

    • 450通过
    • 1.5K提交
  • 题目提供者 XuKaFy
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Life种了一块田,里面种了有一些桃树。

    Life对PFT说:“我给你一定的时间去摘桃,你必须在规定的时间之内回到我面前,否则你摘的桃都要归我吃!”

    PFT思考了一会,最终答应了!

    由于PFT的数学不好!它并不知道怎样才能在规定的时间获得最大的价值,

    由于PFT不是机器人,所以他的体力并不是无限的,他不想摘很多的桃以至体力为0,而白白把桃给Life。同时PFT每次只能摘一棵桃树,,每棵桃树都可以摘K次(对于同一棵桃每次摘的桃数相同)。每次摘完后都要返回出发点(PFT一次拿不了很多)即Life的所在地(0,0){试验田左上角的桃坐标是(1,1)}。

    PFT每秒只能移动一个单位,每移动一个单位耗费体力1(摘取不花费时间和体力,但只限上下左右移动)。

    题目描述

    输入输出格式

    输入格式:

    第一行:四个数为N,M,TI,A 分别表示试验田的长和宽,Life给PFT的时间,和PFT的体力。

    下面一个N行M列的矩阵桃田。表示每次每棵桃树上能摘的桃数。

    接下来N行M列的矩阵,表示每棵桃最多可以采摘的次数K。

    输出格式:

    一个数:PFT可以获得的最大的桃个数。

    输入输出样例

    输入样例#1: 复制
    4 4 13 20
    10 0  0  0
    0  0  10 0
    0  0  10 0
    0  0  0  0
    1 0 0 0
    0 0 2 0
    0 0 4 0
    0 0 0 0
    输出样例#1: 复制
    10

    说明

    样例说明:

    可以摘到1次(1,1)和1次(2,3),体力和时间不满足再摘桃了。

    范围:

    对于M,N,TI,A 10<=30%<=50 10<=100%<=100

    对于K 10<=100%<=100

    保证结果在long int范围内

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