FJoi2017 1月20日模拟赛 恐狼后卫(口糊动规)
Problem 1 恐狼后卫(wolf.cpp/c/pas)
【题目描述】
著名卡牌游戏《石炉传说》中有一张随从牌:恐狼后卫。恐狼后卫的能力是使得相邻随从的攻击力提高。
现在有n张恐狼后卫顺序排成一排,第i只恐狼后卫的攻击力为a[i],血量为h[i],提升相邻随从的攻击力值为b[i]。
你的攻击力为atk,每次攻击你可以选择一只存活的恐狼后卫,减少其血量值atk。若其血量小于等于0,则该恐狼后卫死亡。当某只恐狼后卫死亡时,其左右两侧(若存在)的恐狼后卫会靠拢并成为相邻关系。
在攻击第i只恐狼后卫时,除了要承受这只恐狼后卫自身的攻击力a[i]之外,还要承受与其相邻的2张恐狼后卫的提高攻击力值b[i-1]和b[i+1](若存在)。
你的任务是承受最少的总伤害杀死所有恐狼后卫,输出需承受的伤害值。
【输入格式】
第一行一个正整数n,表示恐狼后卫的数量。
第二行一个正整数atk,表示你的攻击力。
以下n行,每行3个值:a[i]、b[i]、h[i],分别表示第i只恐狼后卫自身的攻击力值、提升相邻随从的攻击力值、血量值。
【输出格式】
一个整数,表示杀死所有恐狼后卫需要承受的最少伤害值。
【样例输入】
3
1
8
1 6
3
5 7
4
9 2
【样例输出】
94
【数据范围】
对于30%的数据,n
<= 10
对于另外30%的数据,n
<= 100, h[i] = 1
对于100%的数据,n
<= 400,atk、a[i]、b[i]、h[i]
<= 1000
很简单,区间动规嘛,我这样的juruo都现场ac了。设状态f[i][j]代表开区间(i,j)内的东东被全部杀掉的代价。
转移方程为f[i][j]=min{f[i][k]+f[k][j]+attack[k]+improvement[i]+improvement[j]}
省选培训第二次模拟赛rank20+,果然我还是太弱
最新文章
- SQL Server2008 错误源:.net SqlClient data provider的解决方法
- C#中获取程序集版本号的方法
- Linux下 RabbitMQ的安装与配置
- PHP 性能分析与实验——性能的宏观分析
- hdu 1045 Fire Net(最小覆盖点+构图(缩点))
- 将表中数据生成SQL语句
- 你所不知道的 URL
- asp.net导出Excel 按照预定格式,以及解决导出乱码
- DES 算法的 C++ 与 JAVA 互相加解密
- js template
- C#和SQL操作Xml
- if....else
- 漫游Ruby
- 肢体语言心理学+FBI阅人术(行为心理学) 用最短的时间了解一个人
- PHP实现的进度条效果详解
- 泛型的 typeof
- OpenGL编程指南(第九版) Tiangles 学习笔记
- maven安装与基本配置
- liunx一键安装禅道
- C++ 基础知识回顾总结
热门文章
- bzoj 2017: [Usaco2009 Nov]硬币游戏【dp】
- 17年day3
- python实现对某招聘网接口测试获取平台信息
- 使用 typescript 和 canvas 重构snow效果
- $Hdu1381\ Crazy\ Search$
- 407 Trapping Rain Water II 接雨水 II
- python使用mysql connection获取数据感知不到数据变化问题
- mybatis之多个对象自动装配问题
- sublime text 3 使用技巧
- EasyUI系列学习(七)-Linkbutton(按钮)