P6750: 恐狼后卫
传统题
1.000s
时间限制
256MB
内存限制
3 提交
1 解决
【题目描述】
著名卡牌游戏《石炉传说》中有一张随从牌：恐狼后卫。恐狼后卫的能力是 使得相邻随从的攻击力提高。
现在有 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 只恐狼后卫自身 的攻击力值、提升相邻随从的攻击力值、血量值。
【输出格式】
一个整数，表示杀死所有恐狼后卫需要承受的最少伤害值。
样例输入
input
3
1
8 1 6
3 5 7
4 9 2
output
94
数据范围
对于30%的数据， n<=10
对于另外30%的数据，n<=100,h[i]=1
对于100%的数据，n<=400,atk、a[i]、b[i]、h[i]<=1000