阿里巴巴 Alibaba
UVA1632
这是一个区间动态规划
定义：$dp[i][j][0]$为阿里巴巴收集完$i$到$j$的宝藏后位于$i$位置的最短耗时，$dp[i][j][1]$为阿里巴巴收集完$i$到$j$的宝藏后位于$j$位置的最短耗时。（在最短耗时情况下，阿里巴巴收集完某个区间的宝藏后只能位于区间的边缘，不可能在内部，因为在内部的话，必有重复经过的点，而在边缘，直接从一端到另一端即可）。
初始化：
即阿里巴巴在某地都可以瞬间收集宝藏。
转移方程：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19dp[i][j][0] = min(
//从i+1处向左走到i
dp[i + 1][j][0] + Treasures[i + 1].Location - Treasures[i].Location,
//从j处向左走到i
dp[i + 1][j][1] + Treasures[j].Location - Treasures[i].Location
);
//如果最短时间超时，则设为不可达
if (dp[i][j][0] >= Treasures[i].Limit) {
dp[i][j][0] = inf;
}
//从i向右走到j
dp[i][j][1] = min(
dp[i][j - 1][0] + Treasures[j].Location - Treasures[i].Location,
//从j-1向右走到j
dp[i][j - 1][1] + Treasures[j].Location - Treasures[j - 1].Location
);
//超时判定
if (dp[i][j][1] >= Treasures[j].Limit) {
dp[i][j][1] = inf;
AC代码：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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
constexpr static int inf = 0x3f3f3f3f;
int dp[10001][10001][2];
struct {
int Location, Limit;
}Treasures[10001];
int N;
bool Input() {
if (scanf("%d", &N) == EOF) {
return false;
}
for (int i = 1; i <= N; ++i) {
scanf("%d %d", &Treasures[i].Location, &Treasures[i].Limit);
}
return true;
}
void Init() {
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= N; ++i) {
dp[i][i][0] = dp[i][i][1] = 0;
}
}
int DP() {
for (int Section = 2; Section <= N; ++Section) {
for (int i = 1; i <= N; ++i) {
int&& j = i + Section - 1;
if (j > N) {
continue;
}
dp[i][j][0] = min(
dp[i + 1][j][0] + Treasures[i + 1].Location - Treasures[i].Location,
dp[i + 1][j][1] + Treasures[j].Location - Treasures[i].Location
);
if (dp[i][j][0] >= Treasures[i].Limit) {
dp[i][j][0] = inf;
}
dp[i][j][1] = min(
dp[i][j - 1][0] + Treasures[j].Location - Treasures[i].Location,
dp[i][j - 1][1] + Treasures[j].Location - Treasures[j - 1].Location
);
if (dp[i][j][1] >= Treasures[j].Limit) {
dp[i][j][1] = inf;
}
}
}
return min(dp[1][N][0], dp[1][N][1]);
}
int main() {
while (Input()) {
Init();
int&& Ans = DP();
if (Ans == inf) {
puts("No solution");
}
else {
printf("%d\n", Ans);
}
}
return 0;
}
2.86秒险过。。。那么，优化一下吧。
发现对于相同的区间长度，$dp[i]$的状态都由$dp[i+1]$或$dp[i]$得到，并且$i$是递增的，因此可以滚动数组优化。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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
constexpr static int inf = 0x3f3f3f3f;
int dp[2][10001][2];
struct {
int Location, Limit;
}Treasures[10001];
int N;
bool Input() {
if (scanf("%d", &N) == EOF) {
return false;
}
for (int i = 1; i <= N; ++i) {
scanf("%d %d", &Treasures[i].Location, &Treasures[i].Limit);
}
return true;
}
void Init() {
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= N; ++i) {
dp[0][i][0] = dp[0][i][1] = dp[1][i][0]=dp[1][i][1]=0;
}
}
int DP() {
for (int Section = 2; Section <= N; ++Section) {
for (int i = 1; i <= N + 1 - Section; ++i) {
int&& j = i + Section - 1;
int& Ans1 = dp[i & 1][j][0];
Ans1 = min(
dp[(i + 1)&1][j][0] + Treasures[i + 1].Location - Treasures[i].Location,
dp[(i + 1)&1][j][1] + Treasures[j].Location - Treasures[i].Location
);
if (Ans1 >= Treasures[i].Limit) {
Ans1 = inf;
}
int& Ans2 = dp[i & 1][j][1];
Ans2 = min(
dp[i & 1][j - 1][0] + Treasures[j].Location - Treasures[i].Location,
dp[i & 1][j - 1][1] + Treasures[j].Location - Treasures[j - 1].Location
);
if (Ans2 >= Treasures[j].Limit) {
Ans2 = inf;
}
}
}
return min(dp[1][N][0], dp[1][N][1]);
}
int main() {
while (Input()) {
Init();
int&& Ans = DP();
if (Ans == inf) {
puts("No solution");
}
else {
printf("%d\n", Ans);
}
}
return 0;
}
时间复杂度没变，但是这次只需要0.39秒，也许是是cache优化？
