晦涩的题意＋各种傻逼害我调了那么久，实际上题目就是一个dp[i][j]，dp[i][j]表示第i层第j个最少需要多少时间，当我们去更新dp[i][j]的时候，考虑的是从第i+1层的某一个dp[i+1][k]往上顶一层，然后走到dp[i][j]的位置，当然往上跳的时候要注意不要碰到怪物墙壁，各种坑，我的码力果然不行呀－ －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
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83 |
#pragma warning(disable:4996)#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<vector>#include<cmath>#define maxn 2500#define maxw 220using
namespace std;int
dp[maxn][maxw];char
num[maxn][maxw];char
type[maxn][maxw];int
n, w;int
t1, t2, t3;int
main(){ while
(cin >> n >> w) { scanf("%d%d%d", &t1, &t2, &t3); for
(int i = 1; i <= n; i++){ scanf("%s", type[i] + 1); scanf("%s", num[i] + 1); } memset(dp, 0x3f, sizeof(dp)); dp[n][1] = 0; int
tmp = 0; //if (type[n][1] == ‘|‘ || num[n][1] == ‘0‘||type[n][1]==‘#‘) dp[n][1] = 0x3f3f3f3f; for
(int i = 2; i <= w; i++){ if
(dp[n][1] == 0x3f3f3f3f) break; if
(type[n][i] == ‘|‘
|| num[n][i] == ‘0‘){ break; } if
(type[n][i] == ‘#‘) tmp += t3; tmp += t1; dp[n][i] = tmp; } for
(int i = n - 1; i >= 1; i--){ for
(int j = 1; j <= w; j++){ if
(type[i][j] == ‘|‘||num[i][j]==‘0‘) continue; int
k = j - 1; int
cost = 0; if
(type[i][j] == ‘#‘) cost += t3; bool
flag = false; while
(k >= 1){ if
(type[i][k] == ‘|‘) break; if
(num[i][k] == ‘0‘){ flag = true; } if
(type[i][k +1] != ‘#‘) dp[i][j] = min(dp[i][j], dp[i + 1][k] + cost + (num[i][k] - ‘0‘
+ 1)*t2); if
(type[i][k] == ‘#‘) cost += t3; cost += t1; k--; if
(flag) break; } k = j + 1; cost = 0; flag = false; if
(type[i][j] == ‘#‘) cost += t3; while
(k <= w){ if
(type[i][k] == ‘|‘) break; if
(num[i][k] == ‘0‘){ flag = true; } if
(type[i][k - 1] != ‘#‘) dp[i][j] = min(dp[i][j], dp[i + 1][k] + cost + (num[i][k] - ‘0‘
+ 1)*t2); if
(type[i][k] == ‘#‘) cost += t3; cost += t1; k++; if
(flag) break; } } } int
ans = 0x3f3f3f3f; for
(int i = 1; i <= w; i++){ ans = min(dp[1][i], ans); } if
(ans == 0x3f3f3f3f) puts("-1"); else
cout << ans << endl; } return
0;} |
ZOJ 3555 Ice Climber(dp),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3627408.html