首页 > 代码库 > Hdu5115 Dire Wolf

Hdu5115 Dire Wolf

Hdu5115 Dire Wolf

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

题目大意:n头狼,分别有一个攻击力,而且分别有一个加持力,可以给左右两边的狼加相应的攻击力(边界的狼就只能给相邻的一头狼加) ,一个人要杀狼,杀一头狼时受到该狼的攻击力和来自周围的加持力。被杀死的狼的加持力消失,但其他狼又会更新加持力(因为相邻的位置变化了)。问该人能够把全部狼杀光,且最小受到多少伤害?

/*    dp[i][j]表示从第i头狼到第j头狼全部被杀死的最小伤害     dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+v[k]+w[i-1]+w[j+1]);*/#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;int T,w[220],v[220],n,dp[220][220];int main(){    scanf("%d",&T);    for(int o=1;o<=T;o++){        memset(dp,127/3,sizeof(dp));        memset(v,0,sizeof(v));        memset(w,0,sizeof(w));        scanf("%d",&n);        for(int i=1;i<=n;i++)scanf("%d",&v[i]);        for(int i=1;i<=n;i++)scanf("%d",&w[i]);        for(int i=1;i<=n;i++)dp[i][i]=v[i]+w[i-1]+w[i+1];        for(int i=n-1;i>=1;i--){            for(int j=i+1;j<=n;j++){                dp[i][j]=min(dp[i+1][j]+v[i]+w[i-1]+w[j+1],dp[i][j-1]+v[j]+w[j+1]+w[i-1]);                for(int k=i+1;k<=j-1;k++)                    dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+v[k]+w[i-1]+w[j+1]);            }        }        printf("Case #%d: %d\n",o,dp[1][n]);    }}

 

Hdu5115 Dire Wolf