题目的意思是给你n头狼,然后他们自己有a点攻击,附带b点攻击。在每次攻击一头狼时,旁边两条狼会将附带伤害值加到当前狼上。
意味着你会受到ai+bi-1+bi+1点攻击伤害。求杀死所有的狼你受到的伤害最小值。
比赛的时候觉得dp不好做,因为以前没有接触过区间dp,所以一直拿着贪心在乱搞。
区间dp,对区间长度从1到n,进行dp。随着区间长度的增加,所以遍历的次数可以为:
n-len+1
每次遍历的区间最大值应该是:
i+len-1
最小值是每次的起始本身。
然后假设我们攻击这个区间内任意一只狼,这时相当于其它狼已经被消灭。所以dp方程为:
dp[i][j]=min(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);
dp[i][j]意味着从第i头狼攻击到第j头狼的最小伤害值。大概就是下面这个样子:
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int inf=0x3f3f3f3f-10;
const int maxn = 210;
int a[maxn], b[maxn], dp[maxn][maxn];
int t, n;
int main()
{
scanf("%d", &t);
for(int cas=1;cas<=t;cas++){
scanf("%d", &n);
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d", &b[i]);
}
b[0]=b[n+1]=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
dp[i][j]=inf;
}
}
for(int i=0;i<=n;i++){
dp[0][i]=dp[i][n+1]=0;
}
for(int len=1;len<=n;len++){ //长度为len
for(int i=1;i<=n-len+1;i++){
int j=i+len-1; //遍历长度为len时的区间
for(int k=i;k<=j;k++){ //区间内应该攻击第k只狼(假设其他狼已经died)
dp[i][j]=min(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);
}
}
}
printf("Case #%d: %d\n", cas, dp[1][n]);
}
return 0;
}