Dire Wolf HDU - 5115（区间dp）

dire wolf

time limit: 5000/5000 ms (java/others)    memory limit: 512000/512000 k (java/others)
total submission(s): 3815    accepted submission(s): 2266

problem description

dire wolves, also known as dark wolves, are extraordinarily large and powerful wolves. many, if not all, dire wolves appear to originate from draenor.
dire wolves look like normal wolves, but these creatures are of nearly twice the size. these powerful beasts, 8 - 9 feet long and weighing 600 - 800 pounds, are the most well-known orc mounts. as tall as a man, these great wolves have long tusked jaws that look like they could snap an iron bar. they have burning red eyes. dire wolves are mottled gray or black in color. dire wolves thrive in the northern regions of kalimdor and in mulgore.
dire wolves are efficient pack hunters that kill anything they catch. they prefer to attack in packs, surrounding and flanking a foe when they can.
— wowpedia, your wiki guide to the world of warcra

matt, an adventurer from the eastern kingdoms, meets a pack of dire wolves. there are n wolves standing in a row (numbered with 1 to n from left to right). matt has to defeat all of them to survive.

once matt defeats a dire wolf, he will take some damage which is equal to the wolf’s current attack. as gregarious beasts, each dire wolf i can increase its adjacent wolves’ attack by b_i. thus, each dire wolf i’s current attack consists of two parts, its basic attack ai and the extra attack provided by the current adjacent wolves. the increase of attack is temporary. once a wolf is defeated, its adjacent wolves will no longer get extra attack from it. however, these two wolves (if exist) will become adjacent to each other now.

for example, suppose there are 3 dire wolves standing in a row, whose basic attacks ai are (3, 5, 7), respectively. the extra attacks b_i they can provide are (8, 2, 0). thus, the current attacks of them are (5, 13, 9). if matt defeats the second wolf first, he will get 13 points of damage and the alive wolves’ current attacks become (3, 15).

as an alert and resourceful adventurer, matt can decide the order of the dire wolves he defeats. therefore, he wants to know the least damage he has to take to defeat all the wolves.

 

 

input

the first line contains only one integer t , which indicates the number of test cases. for each test case, the first line contains only one integer n (2 ≤ n ≤ 200).

the second line contains n integers a_i (0 ≤ a_i ≤ 100000), denoting the basic attack of each dire wolf.

the third line contains n integers b_i (0 ≤ b_i ≤ 50000), denoting the extra attack each dire wolf can provide.

 

 

output

for each test case, output a single line “case #x: y”, where x is the case number (starting from 1), y is the least damage matt needs to take.

 

 

sample input

2

3

3 5 7

8 2 0

10

1 3 5 7 9 2 4 6 8 10

9 4 1 2 1 2 1 4 5 1

 

 

sample output

case #1: 17

case #2: 74

hint

in the first sample, matt defeats the dire wolves from left to right. he takes 5 + 5 + 7 = 17 points of damage which is the least damage he has to take.

 

题目大意：你是一个战士现在面对，一群狼，每只狼都有一定的主动攻击力和附带攻击力。你杀死一只狼。你会受到这只狼的（主动攻击力+旁边两只狼的附带攻击力）这么多伤害~现在问你如何选择杀狼的顺序使的杀完所有狼时，自己受到的伤害最小。（提醒，狼杀死后就消失，身边原本相隔的两只狼会变成相邻，而且不需要考虑狼围城环这种情况）

输入要求：总共t组数据，每组n只狼，按顺序输入全部狼的主动攻击力和然后再按顺序输入全部狼的附带攻击力

输出要求：case #x: y x第几组数据，y最少受到的伤害

样例解释： 
2

输入 
3 
3 5 7 
8 2 0 
输出 
case #1: 17 
杀序号1的狼 3+2=5 
杀序号2的狼 5+0=5 
杀序号3的狼 7+0=7 
总的伤害5+5+7=17；

10 
1 3 5 7 9 2 4 6 8 10 
9 4 1 2 1 2 1 4 5 1 
case #2: 74 
主动伤害总和1+3+5+7+9+2+4+6+8+10=55； 
附带伤害总和 
因为数字比较多我这次列出全部过程 
【1】3 5 7 9 2 4 6 8 10 
【9】 4 1 2 1 2 1 4 5 1 
附带伤害 4 
【1 3】 5 7 9 2 4 6 8 10 
【9 4】 1 2 1 2 1 4 5 1 
附带伤害 1 
【1 3 】5 【7】 9 2 4 6 8 10 
【9 4】 1 【2】 1 2 1 4 5 1 
附带伤害 1+1=2 
【1 3】 5【 7】 9 【2】 4 6 8 10 
【9 4】 1 【2】 1 【2】 1 4 5 1 
附带伤害 1+1=2； 
此时实际序列5 9 4 6 8 10 
1 1 1 4 5 1 
【1 3】 5【 7】 9 【2】 4 6【 8】 10 
【9 4】 1 【2】 1 【2】 1 4 【5】 1 
附带伤害 4+1=5 
【1 3】 5【 7】 9 【2】 4【 6 8】 10 
【9 4】 1 【2】 1 【2】 1 【4 5】1 
附带伤害 1+1=2 
剩下4只狼 
5 9 4 10 
1 1 1 1 
从左边杀起，因这样每次只有右边有附带伤害 
1+1+1=3 
附带伤害总和4+1+2+2+5+2+3=19 
总和伤害55+19=74

 

思路：区间dp，用贪心竟然wa了，肯定哪里有错了，呜呜呜

 

区间dp的伪代码

//mst(dp,0) 初始化dp数组
for(int i=1;i<=n;i++)
{
    dp[i][i]=初始值
}
for(int len=2;len<=n;len++)  //区间长度
for(int i=1;i<=n;i++)        //枚举起点
{
    int j=i+len-1;           //区间终点
    if(j>n) break;           //越界结束
    for(int k=i;k<j;k++)     //枚举分割点，构造状态转移方程
    {
        dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
    }
}

 

题目ac代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define eps 1e-10
#define ll long long
int const maxn = 205;
const int mod = 1e9 + 7;
int gcd(int a, int b) {
    if (b == 0) return a;  return gcd(b, a % b);
}

int attack[210];
int extre[210];
int dp[210][210];   //第i到第j个的最小受到伤害

int main()
{
    int t;
    cin>>t;
    int ca=1;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>attack[i];
        for(int i=1;i<=n;i++)
            cin>>extre[i];
        extre[0]=0;   //初始边界情况
        extre[n+1]=0;
        for(int i=1;i<=n;i++)

//刚开始我写成memset(dp,inf,sizeof(dp));这样是错的因为下面有dp[i][k-1]+dp[k+1][j]在每次循环时第一遍因为j==k,所以k+1>j

 //  如果按memset初始化，dp[k+1][j]和[dp[i][j]都是超级大的数，min就会出错。

for(int j=i;j<=n;j++) dp[i][j]=inf; for(int i=0;i<=n;i++) 
       {

            dp[0][i]=0;
            dp[i][n+1]=0;
        }
        for(int len=1;len<=n;len++)
            for(int i=1;i<=n;i++)
            {
                
                int j=i+len-1;
                if(j>n)
                    break;
                for(int k=i;k<=j;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+attack[k]+extre[i-1]+extre[j+1]);  
                }
            }
        printf("case #%d: %d\n",ca++,dp[1][n]);
    }
}