HDOJ 5115 Dire Wolf /HZAUOJ 1098 Yifan and War3 (裸区间dp)
云宾鸿
Dire Wolf
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 2089 Accepted Submission(s): 1204
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.
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.
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: 74HintIn 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.
Source
Recommend
liuyiding
1098: Yifan and War3
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 611 Solved: 15
[ Submit][ Status][ Web Board]
Description
As we all know, There is a hero called Priestess of the Moon(POM), which has a passive ability named Trueshot Aura . It can add other units some ranged attacks . Fanfan love the Human very much, and he will battle with a Night Elf everyday , because he thinks the Night Elf can’t attack his tower easily .But today , he met a Night Elf player , who use POM as his first hero, and had lots of Archers . Fanfan use theMountain King to kill the Archers ,and don’t know how many health he need to kill all the Archers .Could you help him ?
To make the problem simple , we assume that all the Archers stand in a line , they have different attacks , if Fanfan kills the ith Archer , the (i+1)th and the (i-1)th Archer will help to attack Fanan by their own attacks . There are N Archers , and Fanfan wants to know the least damage he will get to kill all the Archers .
Input
First line contains an integer N (0<N<200), means there are N Archers .
Then the next line contains N integers ai(0<ai<100000) means that the ith Archers have ai attacks .
Output
An integer means the least damage Fanfan will get.
Sample Input
3 10 100 10
Sample Output
150
HINT
Yifan first kill the second Archer , get 100+10+10 demages , and then kill the first one ,get 10+10 demages and finally kill the third one and get 10 demages so , he get 150 demage
题意：
大意就是每次攻击一个敌人时，都会收到它两边的敌人的攻击，也就是攻击增益。然后问你怎么打，才能受到最小伤害。
HDOJ 的Dire Wolf是2014年ICPC北京的一道题，而Yifan and War3则是HZAU的新生赛题（尼玛新生赛就来区间dp）。
大体思路就是进行区间dp找最小伤害的那个dp值。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdlib>
using namespace std;
const int maxn=200+5;
int t,n;
int a[maxn];
int b[maxn];
int dp[maxn][maxn];
int ddp(int i,int j)
{
if (dp[i][j]!=-1) return dp[i][j];
if (i==j) return dp[i][j]=a[i]+b[i-1]+b[i+1];
int tmp1=ddp(i,j-1)+a[j]+b[i-1]+b[j+1];
int tmp2=ddp(i+1,j)+a[i]+b[i-1]+b[j+1];
int tmp;
int ans=min(tmp1,tmp2);
for(int k=i+1;k<j;k++){
tmp=ddp(i,k-1)+ddp(k+1,j)+a[k]+b[i-1]+b[j+1];
ans=min(ans,tmp);
}
return dp[i][j]=ans;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=0;a[n+1]=0;
b[0]=0;b[n+1]=0;
for(int i=1;i<=n;i++) b[i]=a[i];
memset(dp,-1,sizeof(dp));
printf("%d\n",ddp(1,n));
}
return 0;
}
/**************************************************************
Problem: 1098
User: 2016_hhu09
Language: C++
Result: Accepted
Time:1695 ms
Memory:1668 kb
****************************************************************/
类似资料：