华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1896|回复: 1
打印 上一主题 下一主题

2717: 恐狼后卫

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2021-10-19 17:32:19 | 只看该作者 回帖奖励 |正序浏览 |阅读模式
【题目描述】

著名卡牌游戏《石炉传说》中有一张随从牌:恐狼后卫。恐狼后卫的能力是使得相邻随从的攻击力提高。
现在有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
回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 2021-10-19 17:32:37 | 只看该作者
对于30%的数据,n <= 10,直接穷举所有情况即可。

对于另外30%的数据,n <= 100, h[i] = 1
首先本题中的a[]直接求和即可,只需要考虑b[]的影响。常规的解决该类问题的思路是区间DP,枚举第一个去掉的位置并将问题转化为左右两个子区间的问题,而本题的关键是在杀死一只恐狼后卫后,其相邻两侧的恐狼后卫会靠拢,且恐狼后卫能提升相邻的随从的攻击力。所以如若枚举区间内第一个杀死的恐狼后卫,左右两区间的相邻的恐狼会互相影响,所以并不是一个子问题。此时应反其道而行之,枚举最后一只杀死的狼,在这种情况左右两个子区间被这最后一只狼隔开,就成为了2个子问题。
详细描述一遍,设f[i][j]为消灭第i只到第j只恐狼的最优代价(被第i-1只狼和第j+1只狼包围),枚举k作为最后一只被杀死的狼,则在杀死这第k只狼时,将会受到第i-1只狼和第j+1只狼的攻击力提升。
f[i][j]=Min(f[i][k-1]+f[k+1][j]+b[i-1]+b[j+1])
这是O(n^3)的DP,可以顺利解决。

对于100%的数据,恐狼有血量值,可以先根据玩家的攻击力atk换算出攻击次数。用贪心思想易得,存在一个最优方案:攻击某只恐狼必连续攻击至死,再攻击别的恐狼。所以DP方程略微修改为:
f[i][j]=Min(f[i][k-1]+f[k+1][j]+ (b[i-1]+b[j+1]) * times[k])
其中times[k]为杀死第k只狼需要的攻击次数。


回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:11 , Processed in 0.198471 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表