题目描述
http://acm.hdu.edu.cn/showproblem.php?pid=5115
区间dp经典题
Solution
首先简单证明一下为什么可以按照区间杀狼
简单来想如果不是按照区间来杀的话，完全可以换成按照区间来杀
因为如果不是按照区间来的话，交换顺序是不影响的
那么我们令f[i][j]表示杀光区间[i,j]的狼的最小伤害
转移枚举中间点k即可
时间复杂度 $O(n^3)$
在贴正确代码之前先贴一个样例都过不了的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <cstdio>
#define maxn 210
#define INF 1000000000
using namespace std;
int n, a[maxn], b[maxn];
int f[maxn][maxn];
void work() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i]; b[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
f[i][i] = a[i] + b[i - 1] + b[i + 1];
if (i < n) f[i][i + 1] = a[i] + a[i + 1] + b[i - 1] + b[i + 2]
+ min(b[i] + b[i + 2], b[i + 1] + b[i - 1]);
}
for (int l = 3; l <= n; ++l)
for (int i = 1; i + l - 1 <= n; ++i) {
int j = i + l - 1; f[i][j] = INF;
for (int k = i + 1; k < j; ++k)
f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[k] + b[i - 1] + b[j + 1]);
}
cout << f[1][n] << endl;
}
int main() {
int t; cin >> t;
while (t--) work();
return 0;
}
|
正确答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <cstdio>
#define maxn 210
#define INF 1000000000
using namespace std;
int n, a[maxn], b[maxn];
int f[maxn][maxn], icase;
void work() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i]; b[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
f[i][i] = a[i] + b[i - 1] + b[i + 1];
if (i < n) f[i][i + 1] = a[i] + a[i + 1] + b[i - 1] + b[i + 2]
+ min(b[i] + b[i + 2], b[i + 1] + b[i - 1]);
}
for (int l = 3; l <= n; ++l)
for (int i = 1; i + l - 1 <= n; ++i) {
int j = i + l - 1; f[i][j] = min(f[i + 1][j] + a[i], f[i][j - 1] + a[j]) + b[i - 1] + b[j + 1];
for (int k = i + 1; k < j; ++k)
f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[k] + b[i - 1] + b[j + 1]);
}
printf("Case #%d: %d\n", ++icase, f[1][n]);
}
int main() {
int t; cin >> t;
while (t--) work();
return 0;
}
|