#P1707. 【算法】【15】绝地反杀
【算法】【15】绝地反杀
问题说明
Gold King家的羊群属于圈养的,但到一年中的夏季就会有一次外出放养的机会。Gold King赶着羊群往草原腹地的草场进发,阵容浩大的队伍,引起了狼群的注意。有n头狼赶到了队伍前,准备冲向羊群,每头狼有一个攻击值ai,并且是一字排开的阵型,所以每只狼会给旁边的狼一个buff加成bi,Gold King只有消灭狼群,才能挽救羊群,杀死其中一只狼,需要承受这只狼的伤害和两边buff加成伤害,这只狼被杀死之后,它对应的buff加成会消失。
例如:有3只狼,对应攻击力为(3,5,7),buff加成(8,2,0), 最后得到综合攻击力(5,13,9),假如Gold King先消灭中间那只,会受到13点伤害,剩余狼群综合攻击力为(3,15)。
请问Gold King最少承受多少伤害。
输入格式
第一行输入一个整数你,表示有n只狼。第二行输入n个数据,表示狼的基本攻击力。
第三行输入n个数据,表示对应buff加成值。
输出格式
输出一个整数值,表示Gold King承受的最少伤害值。样例1输入:
3
3 5 7
8 2 0
样例2输入:
10
1 3 5 7 9 2 4 6 8 10
9 4 1 2 1 2 1 4 5 1
样例1输出:
17
样例2输出:
74
提示
2<=n<=2000<=ai<=100000
0<=bi<=50000
样例1,Gold King从左向右消灭狼,5+5+7=17。
来源/分类
算法培训-15-区间动态规划统计
相关
在以下作业中: