题目描述
著名卡牌游戏《石炉传说》中有一张随从牌：恐狼后卫。
恐狼后卫的能力是 使得相邻随从的攻击力提高。 现在有 n 张恐狼后卫顺序排成一排，第 i 只恐狼后卫的攻击力为 ai，血 量为 hi，提升相邻随从的攻击力值为 bi。 你的攻击力为 atk，每次攻击你可以选择一只存活的恐狼后卫，减少其血量 值 atk。
若其血量小于等于 0，则该恐狼后卫死亡。当某只恐狼后卫死亡时，其 左右两侧（若存在）的恐狼后卫会靠拢并成为相邻关系。 在攻击第 i 只恐狼后卫时，除了要承受这只恐狼后卫自身的攻击力 ai之 外，还要承受与其相邻的 2 张恐狼后卫的提高攻击力值 bi-1 和 bi+1（若存 在） 。 你的任务是承受最少的总伤害杀死所有恐狼后卫，输出需承受的伤害值。
输入格式
第一行一个正整数 n，表示恐狼后卫的数量。 第二行一个正整数 atk，表示你的攻击力。
以下 n 行，每行 3 个值：ai、bi、hi，分别表示第 i 只恐狼后卫自身 的攻击力值、提升相邻随从的攻击力值、血量值。
输出格式
一个整数，表示杀死所有恐狼后卫需要承受的最少伤害值。
样例输入
3
1
8 1 6
3 5 7
4 9 2样例输出
94数据范围
对于 30%的数据，n <= 10
对于另外 30%的数据，n <= 100, h[i] = 1
题目链接:http://192.168.68.33/problem/121
解题报告
首先,这题非常明显是区间DP,
定义方程f[l][r]表示消灭l~r号狼的最小代价.
先枚举区间长度,从小到大,复杂度O(n),
再枚举区间左端点,复杂度为O(n),
那么区间右端点便确定下来了,
那么一个区间也被确定下来了.
接着在枚举区间断点,
当前区间由哪两段大区间内的相邻的小区间构成,并选取最小代价.
则状态转移方程为
f[l][r]=min(f[l][r],(a[i]+b[l-1]+b[r+1])*(a%b==0?(a/b):(a/b+1))+f[l][i-1]+f[i+1][r]).
所以总复杂度为O(n3).
AC代码如下:
#include<iostream>
#include<cstdio>
#define FOR(i,s,t) for(register int i=s;i<=t;i++)
#define INF 1<<30
using namespace std;
int f[1001][1001];
int a[1001],b[1001],h[1001];
int n,begin;
inline int work(int a,int b){
return a%b==0?(a/b):(a/b+1);
}
int main(){
scanf("%d%d",&n,&begin);
FOR(i,1,n)
scanf("%d%d%d",&a[i],&b[i],&h[i]);
FOR(i,1,n)
f[i][i]=(a[i]+b[i-1]+b[i+1])*work(h[i],begin);
FOR(len,1,n)
FOR(l,1,n){
int r=l+len;
f[l][r]=INF;
FOR(i,l,r)
f[l][r]=min(f[l][r],(a[i]+b[l-1]+b[r+1])*work(h[i],begin)+f[l][i-1]+f[i+1][r]);
}
printf("%d
",f[1][n]);
return 0;
}