ICPC 7305 Jumping Joey

acm dp

在最佳情況下

  1. 從後面開始, pads 之 間的距離越長越好, 那前間就有更多拉繩子的空間
  2. 不用在意 pads 的實際位置, 重要的是距離, 因為他決定了能不能跳
  3. 只要不違反繩子的限制, pads 的所有移位都是可行的

從後面開始想, 如果繩子 <= D, 那把他拉直(因為 1 ), 再跳
不然的有兩個選擇, 拉到D再跳, 或完全拉直再游

tight 指有多少段繩子被拉到 <= D 的最長長度

dp 不等於 pads 的位置, 因為他可能比 pad[n+1]-pad[0] 更大, 但那不要緊, 因為不影響結果

icpc7305.cpp
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

#include <cstdio>
#include <cstring>

int pad[1100];
int ropes[1100];
int dp[1100][1100];

// Think from back to front
// Don't care the real distance, only care the ropes distance.
// The best case,
// as more tight rope (we don't say it is tight if it cannot jump) and long distance as possible, start from last rope
// then it can let the earlier pods have more to pull and jump
// if r[i] <= D, must pull r[i], it still can jump after pull
// else it can pull D or swim (if swim in this point, it mean we can pull this pod in previous pod unitl this ropes tight)

int main() {
	// freopen("input.txt", "r", stdin);

	int T;
	int n, D;

	scanf("%d", &T);
	for (int nt = 1; nt <= T; ++nt) {
		memset(dp, -1, sizeof(dp));

		scanf("%d%d", &n, &D);
		for (int i = 0; i <= n + 1; ++i) scanf("%d", &pad[i]);
		for (int i = 0; i <= n; ++i) scanf("%d", &ropes[i]);

		// dp[k][r]  k = tighted ropes, r = from r to n

		dp[0][n+1] = 0;
		for(int r = n; r >= 0; --r)
			if(ropes[r] <= D) {
				for(int i = 1; i < n+2; ++i)
					if(dp[i-1][r+1] != -1 && dp[i-1][r+1] + ropes[r] >= pad[n+1] - pad[r])
						dp[i][r] = dp[i-1][r+1] + ropes[r];
			} else {
				// pull
				for(int i = 1; i < n+2; ++i)
					if(dp[i-1][r+1] != -1 && dp[i-1][r+1] + D >= pad[n+1] - pad[r])
						dp[i][r] = dp[i-1][r+1] + D;
				// swim
				for(int i = 0; i < n+2; ++i)
					if(dp[i][r+1] != -1 && dp[i][r+1] + ropes[r] >= pad[n+1] - pad[r])
						if(dp[i][r] < dp[i][r+1] + ropes[r])
							dp[i][r] = dp[i][r+1] + ropes[r];
			}
		int tight = 0;
		for(tight = n+1; tight >= 0 && dp[tight][0] == -1; --tight);

		printf("Case %d: %d\n", nt, n+1-tight);
	}
	return 0;
}