要点:状态必然包含区间是哪个[i,j],通过枚举区间分界点进行转移。
也就是说一个大区间是由两个子区间合并来的或者是两个子区间加上中间元素合并来的! 在合并
的时候自然是要满足最优化原理和无后效性原则......
不能多说,到题目中去体会!
这类问题经常会遇到环,环的处理办法通常有两种:
謱)加倍——将数据复制加倍,就可以保证最后一个与第一个相连;
謲)取余——在调用数组时对譮取余。
有可能需要提前处理合并区间的费用,如何处理视情况而定,不要忘记预处理和前缀和的办法!
也就是说一个大区间是由两个子区间合并来的或者是两个子区间加上中间元素合并来的! 在合并
的时候自然是要满足最优化原理和无后效性原则......
不能多说,到题目中去体会!
这类问题经常会遇到环,环的处理办法通常有两种:
謱)加倍——将数据复制加倍,就可以保证最后一个与第一个相连;
謲)取余——在调用数组时对譮取余。
有可能需要提前处理合并区间的费用,如何处理视情况而定,不要忘记预处理和前缀和的办法!
例题：
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.
InputThe 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).
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.
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. OutputFor 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 1Sample 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.
区间DP
由于两端的状态会对其产生影响，则利用dp[i][j]表示i->j段最小值，其包含两端状态对其的影响。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const ll INF = 1e18+5;
int a[205];
int b[205];
ll dp[205][205];
int T,n;
int main()
{
// freopen("data.txt","r",stdin);
scanf("%d",&T);
for(int cas = 1 ; cas <= T ; cas++)
{
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
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]);
}
for(int i=1;i<=n;i++)
{
dp[i][i] = a[i] + b[i-1] + b[i+1];
}
for(int i=2;i<=n;i++)
{
for(int st=1;st<=n-i+1;st++)
{
int en = st+i-1;
dp[st][en] = INF;
for(int k=st+1;k<en;k++)
{
dp[st][en] = min(dp[st][en] , a[k] + b[en+1] + b[st-1] + dp[st][k-1] + dp[k+1][en]);
}
dp[st][en] = min(dp[st][en] , a[en] + b[en+1] + b[st-1] + dp[st][en-1] );
dp[st][en] = min(dp[st][en] , a[st] + b[en+1] + b[st-1] + dp[st+1][en]);
}
}
printf("Case #%d: %lld\n",cas,dp[1][n]);
}
return 0;
}