题目
hdu5115
题意：
有 n 头狼，打死一头狼，将受到与该狼当前攻击相同的伤害 + 当前相邻狼提供的额外攻击。并且该狼的相邻狼相邻（即有5头狼，打死了第二头狼，那么第一头和第三头相邻）。可以决定击败狼的次序。计算打败所有狼所需的最少伤害。
思路：
在区间[ i ，j ]内：
d
p
[
i
]
[
j
]
=
min
k
=
i
j
d
p
[
i
]
[
k
−
1
]
+
d
p
[
k
+
1
]
[
j
]
+
a
[
k
]
+
b
[
i
−
1
]
+
b
[
j
+
1
]
dp[i][j]=\min_{k=i}^{j}dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]
dp[i][j]=k=iminjdp[i][k−1]+dp[k+1][j]+a[k]+b[i−1]+b[j+1]
代码
#include <iostream>
#include <algorithm>
#define DEBUG freopen("_in.txt", "r", stdin); freopen("_out1.txt", "w", stdout);
#define CASEE int t; cin >> t; for (int ti = 1; ti <= t; ti++)
using namespace std;
const int MAXN = 210;
const int INF = 1e9;
int a[MAXN], b[MAXN], dp[MAXN][MAXN];
void solve(){
int n;
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]);
b[n+1] = 0;
for (int i = 1; i <= n; i++)
dp[i][i] = a[i] + b[i-1] + b[i+1];
for (int len = 1; len < n; len++)
for (int i = 1; i <= n - len; i++){
int j = i + len;
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("%d\n", dp[1][n]);
}
int main(){
CASEE{
printf("Case #%d: ", ti);
solve();
}
return 0;
}