HDU5115：Dire Wolf——题解+翻译

http://acm.hdu.edu.cn/showproblem.php?pid=5115

题目大意：给n匹狼，每一次攻击可以秒杀一匹狼，但同时会受到这匹狼的a攻击和它相邻两只狼的b攻击。

给定a，b，求受伤最小的方案。

————————————————————————

乘法游戏进化版，加法游戏。

基本和乘法游戏一致，详情请见这个题解。

简单讲一下思路：dp[i][j]表示在整个大问题内将i～j的狼消灭完需要受多少伤害。

那么显然我们枚举最后一个被消灭的狼，递归左右，则最后一匹狼的攻击为左边界之左，右边界之右的b和它本身的a。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=220;
const int INF=2147483647;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int dp[N][N],a[N],b[N];
int main(){
    int t=read();
    for(int num=1;num<=t;num++){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int l=1;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
        int j=i+l-1;
        dp[i][j]=INF;
        for(int k=i;k<=j;k++){
            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",num,dp[1][n]);
    }
    return 0;
}