1 /*
2 简单递推DP:读题烦!在区间内的都更新一遍,dp[]初始化INF
3 注意:s1与s2大小不一定,坑!
4 详细解释:http://blog.csdn.net/kk303/article/details/6847948
5 */
6 #include <cstdio>
7 #include <iostream>
8 #include <algorithm>
9 #include <cstring>
10 #include <string>
11 #include <queue>
12 using namespace std;
13
14 const int MAXN = 1e4 + 10;
15 const int INF = 0x3f3f3f3f;
16 int C[4], L[4];
17 int dp[MAXN], a[MAXN];
18
19 int main(void) //URAL 1031 Railway Tickets
20 {
21 //freopen ("Y.in", "r", stdin);
22
23 while (scanf ("%d%d%d%d%d%d", &L[1], &L[2], &L[3], &C[1], &C[2], &C[3]) == 6)
24 {
25 int n; scanf ("%d", &n);
26 int s1, s2;
27 scanf ("%d%d", &s1, &s2);
28 if (s1 > s2) swap (s1, s2);
29 a[1] = 0;
30 for (int i=2; i<=n; ++i)
31 {
32 scanf ("%d", &a[i]); dp[i] = INF;
33 }
34
35 dp[s1] = 0;
36 for (int i=s1+1; i<=s2; ++i)
37 {
38 for (int j=1; j<=3; ++j)
39 {
40 int k = i - 1;
41 while (k >= s1)
42 {
43 if (a[i] - a[k] > L[j]) break;
44 if (dp[i] > dp[k] + C[j]) dp[i] = dp[k] + C[j];
45 k--;
46 }
47 }
48 }
49
50 printf ("%d
", dp[s2]);
51 }
52
53 return 0;
54 }
递推DP URAL 1031 Railway Tickets
编译人生,运行世界!