P2198 杀蚂蚁

    • 67通过
    • 286提交
  • 题目提供者 mhlwsk
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 线性结构 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    说“善有善报,恶有恶报,不是不报……”。 小FF一心只顾自己企业的壮大而没顾及自己的采矿业对Greed Island上生态环境的破坏, Greed Island的环境日益恶劣。 终于,岛上的蚂蚁们变异了,它们决定对小FF的矿区进行攻击,欲将岛上的人类驱逐出去……面对蚂蚁们的进攻, 人类节节败退。无奈之下, 小FF请来了全宇宙最强的防御系统制造商派来的工程机器人——SCV,希望能够阻挡蚂蚁的攻势。

    题目描述

    经过小FF的研究,他发现蚂蚁们每次都走同一条长度为n个单位的路线进攻, 且蚂蚁们的经过一个单位长度所需的时间为T秒。也就是说,只要小FF在条路线上布防且给蚂蚁造成沉痛伤害就能阻止蚂蚁的进军。

    SCV擅长制造的防御塔有三种,分别是激光塔,放射塔和干扰塔, 他们可以在一个单位长度内修建一座防御塔。三种防御塔的作用如下:

    激光塔: 使用高能激光,当蚂蚁从塔前经过时每秒对蚂蚁造成r点伤害。

    放射塔: 释放放射性元素, 当蚂蚁经过这座塔后,每一秒受到g点伤害。

    干扰塔: 干扰塔负责干扰蚂蚁们的信息素,使得蚂蚁在经过这座塔后,经过之后每一个单位长度的时间变成T+b。

    当然, 放射塔和干扰塔的效果是可以叠加的, 也就是说如果敌人经过x座放射塔,那么敌人每秒钟会受到x*g点伤害; 同理,如果敌人经过y座干扰塔, 那么敌人经过一个单位长度的时间将变为T+y*b。

    现在距离蚂蚁的下一轮进攻还有足够长的时间,你这个“NewBe_One”计划的首席工程师现在被任命为战略总参谋长, 因此你必须设计一个给蚂蚁们造成最大伤害的布塔方案。

    输入输出格式

    输入格式:

    输入数据仅一行, 5个整数 n, r, g, b, T中间用一个空格隔开。 它们分别表示你可以布防的总长度, 激光塔的效果、 放射塔的效果和干扰塔的效果。

    对于30%的数据: 1<=n<=20;

    对于60%的数据: 1<=n<=1024;

                          0<=r, g, b<=65536;  
    
                          0<=T<=3;

    对于另外40%的数据:

                1<=n<=400;
    
                0<=r, g, b<=2^31-1;

    0<=t<=1000.

    输出格式:

    输出仅一个整数, 代表你的方案给敌人带来的最大伤害值。

    输入输出样例

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

    说明

    输出样例解释:

    第1号位置为放射塔, 第2,3号位置建造干扰塔,第4,5号位置建造激光塔。

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