/*
* 要运送车辆到对岸.车辆已经排好队，注意因为桥窄不能超车，
* 分组的时候不能随意分组，前一组的车辆都排在后一组车辆的前
* 面，即车辆的顺序是按输入固定的。
* 只有一座单行的桥
*
* 每辆车有其重量及最最快车速
*
* 通过分组方式将车辆分成几组运输，
* 每次只能运一组运到对岸后第二组才能出发，
*
* 每组中车辆的总重量不能超过桥的载重量，
*
* 运输速度则取决于该组车辆中最慢的那辆
*
*问如何分组，运输最快
动态规划，从前向后，依次求出到i位置时的最优解，考i位置的时候，考虑i-1,i-2...
* 直到i - j加在一起超过了载重量，则所有这些位置可能性都需要考虑到。
*
* s(i) = min ( (s(i-1) + (i)time), s(i-2) + (i ,i -1)time .. ,s(i - j) + (i , i - 1, ...i - j + 1)time )
*
* w(i) + w(i-1) + ...w(i - j + 1) <= W
* w(i) +.. w(i - j) > w
*
* 可以优化，思路是贪心
* 考虑如果没有速度区别，应该是考虑i位置的时候向前,该组装的越多越好。
* 另外即使有速度不同,s(i) <= s(j),when i < j的事实存在。
* 据此可以优化。 不过优化之后代码稍麻烦，而且提交后发现和没优化用时一样的。 因为复杂度没变还是需要判断那么多，只不过少计算了点，可以再思考如何优化。
1 #include <stdio.h>
2
3 int b,l,n; //b the max weight the bridge can afford, l the bridge length, n cars to transport
4 double r[1001]; // 记录DP算法，到当前位置最优解的最短时间
5 int w[1001]; // 记录各车的重量
6 int s[1001]; // 记录各车的速度
7
8 void SolveDP()
9 {
10 l *= 60; //因为最后求分钟，速度是小时每千米,先*60一样的
11 r[0] = 0;
12
13 int speed, weight;
14 double time_best, time_now;
15
16 for (int i = 1; i <= n; i++) { //从1开始记录下标,r[0] = 0作为哨兵,便于程序统一处理
17
18 scanf("%d%d", &(w[i]), &(s[i]));
19
20 //第一种分组尝试,i单独一组
21 weight = w[i];
22 speed = s[i];
23 time_best = r[i - 1] + (double)l / (double)speed;
24
25 //尝试其它所有可能的包含i的分组
26 for (int j = i - 1; j && (weight += w[j]) <= b; j-- ){
27 if (s[j] < speed)
28 speed = s[j];
29
30 time_now = r[j - 1] + (double)l / (double)speed;
31 if (time_now < time_best)
32 time_best = time_now;
33
34 }
35 r[i] = time_best;
36 }
37 printf("%.1f\n", r[n]);
38 }
39
40 int main(int argc, char *argv[])
41 {
42 while (1) {
43
44 scanf("%d%d%d",&b, &l, &n);
45
46 if (b == 0 && l ==0 && n ==0)
47 break;
48
49 SolveDP();
50 }
51 return 0;
52 }
3 int b,l,n; //b the max weight the bridge can afford, l the bridge length, n cars to transport
4 double r[1001]; // 记录DP算法，到当前位置最优解的最短时间
5 int w[1001]; // 记录各车的重量
6 int s[1001]; // 记录各车的速度
7
8 void SolveDP()
9 {
10 l *= 60; //因为最后求分钟，速度是小时每千米,先*60一样的
11 r[0] = 0;
12
13 int speed, weight;
14 double time_best, time_now;
15
16 for (int i = 1; i <= n; i++) { //从1开始记录下标,r[0] = 0作为哨兵,便于程序统一处理
17
18 scanf("%d%d", &(w[i]), &(s[i]));
19
20 //第一种分组尝试,i单独一组
21 weight = w[i];
22 speed = s[i];
23 time_best = r[i - 1] + (double)l / (double)speed;
24
25 //尝试其它所有可能的包含i的分组
26 for (int j = i - 1; j && (weight += w[j]) <= b; j-- ){
27 if (s[j] < speed)
28 speed = s[j];
29
30 time_now = r[j - 1] + (double)l / (double)speed;
31 if (time_now < time_best)
32 time_best = time_now;
33
34 }
35 r[i] = time_best;
36 }
37 printf("%.1f\n", r[n]);
38 }
39
40 int main(int argc, char *argv[])
41 {
42 while (1) {
43
44 scanf("%d%d%d",&b, &l, &n);
45
46 if (b == 0 && l ==0 && n ==0)
47 break;
48
49 SolveDP();
50 }
51 return 0;
52 }
试图优化
1 #include <stdio.h>
2 const int MaxNum = 1001; //注意因为从1开始，所以需要1000 + 1
3 int b,l,n; //b the max weight the bridge can afford, l the bridge length, n cars to transport
4 double r[1001]; // 记录DP算法，到当前位置最优解的最短时间
5 int w[1001]; // 记录各车的重量
6 int s[1001]; // 记录各车的速度
7
8 void SolveDP()
9 {
10 l *= 60; //因为最后求分钟，速度是小时每千米,先*60一样的
11 r[0] = 0;
12
13 int speed, weight;
14 double time_best, time_now;
15
16 for (int i = 1; i <= n; i++) { //从1开始记录下标,r[0] = 0作为哨兵,便于程序统一处理
17
18 scanf("%d%d", &(w[i]), &(s[i]));
19
20 //第一种分组尝试,i单独一组
21 weight = w[i];
22 speed = s[i];
23 time_best = 1000000; //max TODO why need so large I thought 1000*60 will be OK since l < 1000 s > 1 ??
24
25 //尝试其它所有可能的包含i的分组,注意速度没有下降则肯定更多车辆更优
26 //因为s(i) <= s(j) when i < j ,因此只有速度下降时我们才计算一下到前面
27 //速度对应的最优时间和已有的最优时间对比
28 int j;
29 for (j = i - 1; j && (weight += w[j]) <= b; j-- ){
30 if (s[j] < speed) {
31 time_now = r[j] + (double)l / (double)speed; //分组
.j-1, j|| j + 1i
32 if (time_now < time_best)
33 time_best = time_now;
34 speed = s[j]; // change group sppeed to the lower one
35 }
36 }
37
38 time_now = r[j] + (double)l / (double)speed; //still nedd to deal with the last
39
40 if (time_now < time_best)
41 r[i] = time_now;
42 else
43 r[i] = time_best;
44 }
45
46 printf("%.1f\n", r[n]);
47 }
48
49 int main(int argc, char *argv[])
50 {
51 while (1) {
52
53 scanf("%d%d%d",&b, &l, &n);
54
55 if (b == 0 && l ==0 && n ==0)
56 break;
57
58 SolveDP();
59 }
60 return 0;
61 }
3 int b,l,n; //b the max weight the bridge can afford, l the bridge length, n cars to transport
4 double r[1001]; // 记录DP算法，到当前位置最优解的最短时间
5 int w[1001]; // 记录各车的重量
6 int s[1001]; // 记录各车的速度
7
8 void SolveDP()
9 {
10 l *= 60; //因为最后求分钟，速度是小时每千米,先*60一样的
11 r[0] = 0;
12
13 int speed, weight;
14 double time_best, time_now;
15
16 for (int i = 1; i <= n; i++) { //从1开始记录下标,r[0] = 0作为哨兵,便于程序统一处理
17
18 scanf("%d%d", &(w[i]), &(s[i]));
19
20 //第一种分组尝试,i单独一组
21 weight = w[i];
22 speed = s[i];
23 time_best = 1000000; //max TODO why need so large I thought 1000*60 will be OK since l < 1000 s > 1 ??
24
25 //尝试其它所有可能的包含i的分组,注意速度没有下降则肯定更多车辆更优
26 //因为s(i) <= s(j) when i < j ,因此只有速度下降时我们才计算一下到前面
27 //速度对应的最优时间和已有的最优时间对比
28 int j;
29 for (j = i - 1; j && (weight += w[j]) <= b; j-- ){
30 if (s[j] < speed) {
31 time_now = r[j] + (double)l / (double)speed; //分组
.j-1, j|| j + 1i32 if (time_now < time_best)
33 time_best = time_now;
34 speed = s[j]; // change group sppeed to the lower one
35 }
36 }
37
38 time_now = r[j] + (double)l / (double)speed; //still nedd to deal with the last
39
40 if (time_now < time_best)
41 r[i] = time_now;
42 else
43 r[i] = time_best;
44 }
45
46 printf("%.1f\n", r[n]);
47 }
48
49 int main(int argc, char *argv[])
50 {
51 while (1) {
52
53 scanf("%d%d%d",&b, &l, &n);
54
55 if (b == 0 && l ==0 && n ==0)
56 break;
57
58 SolveDP();
59 }
60 return 0;
61 }
标程
1 #include <stdio.h>
2
3
4 #define MAX_VEHICLES 1000
5
6 typedef struct {
7 int load;
8 double total_time;
9 double group_time;
10 } Record_t;
11
12 Record_t records[MAX_VEHICLES][MAX_VEHICLES + 1];
13
14 int main(void) {
15 int load, length, number, weight, speed, i, j, k;
16 double min_time;
17
18 for (;;)
19 {
20 scanf("%d%d%d", &load, &length, &number);
21 if (!number) break;
22 for (i = 0; i < number; ++i) {
23 scanf("%d%d", &weight, &speed);
24 if (i == 0) {
25 records[0][0].load = weight;
26 records[0][0].total_time = records[0][0].group_time = 60.0*length/speed;
27 j = 1;
28 } else {
29 j = k = 0;
30 min_time = records[i - 1][0].total_time;
31 while (records[i - 1][k].load != 0) {
32 if (min_time > records[i - 1][k].total_time)
33 min_time = records[i - 1][k].total_time;
34 if (records[i - 1][k].load + weight <= load) {
35 records[i][j].load = records[i - 1][k].load + weight;
36 if (records[i - 1][k].group_time >= 60.0*length/speed) {
37 records[i][j].total_time = records[i - 1][k].total_time;
38 records[i][j].group_time = records[i - 1][k].group_time;
39 } else {
40 records[i][j].total_time = records[i - 1][k].total_time
41 + 60.0*length/speed - records[i - 1][k].group_time;
42 records[i][j].group_time = 60.0*length/speed;
43 }
44 ++j;
45 }
46 ++k;
47 }
48 records[i][j].load = weight;
49 records[i][j].total_time = min_time + 60.0*length/speed;
50 records[i][j].group_time = 60.0*length/speed;
51 ++j;
52 }
53 records[i][j].load = 0;
54 }
55 min_time = records[number - 1][0].total_time;
56 i = 1;
57 while (records[number - 1][i].load != 0) {
58 if (records[number - 1][i].total_time < min_time)
59 min_time = records[number - 1][i].total_time;
60 ++i;
61 }
62 printf("%.1f\n", min_time);
63 }
64 return 0;
65