算法导论—动态规划之装配线调度
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;const int maxn = 10000;int f1[maxn], f2[maxn]; //保存最优解int a[3][maxn]; //每个装配站所用的时间int t[3][maxn]; //装配线调度所用的时间int l[3][maxn]; //保存选择的路线，以便打印路径。int e1, e2;int x1, x2;int res;int res1; //代码最后一个装配站的标号是1还是2.int n; // 代表装配线的长度。//P193页（第二版）void init() { scanf("%d%d", &e1, &e2); for(int i = 1; i<=n-1; i++) { scanf("%d%d", &a[1][i], &a[2][i]); scanf("%d%d", &t[1][i], &t[2][i]); } scanf("%d%d", &a[1][n], &a[2][n]); scanf("%d%d", &x1, &x2);}int fast_way(){ f1[1] = e1 + a[1][1]; f2[1] = e2 + a[2][1]; for(int i = 2; i<=n; i++) { if(f1[i-1]+a[1][i] <= f2[i-1]+a[1][i]+t[2][i-1] ) { f1[i] = f1[i-1] + a[1][i]; l[1][i] = 1; }else{ f1[i] = f2[i-1] + a[1][i] + t[2][i-1]; l[1][i] = 2; } if(f2[i-1]+a[2][i] <= f1[i-1]+a[2][i]+t[1][i-1]){ f2[i] = f2[i-1] + a[2][i]; l[2][i] = 2; }else{ f2[i] = f1[i-1] + a[2][i] + t[1][i-1]; l[2][i] = 1; } } if(f1[n]+x1<=f2[n]+x2){ res = f1[n] + x1; res1 = 1; }else{ res = f2[n] + x2; res1 = 2; } return res;}void print_station(){//打印路径 int i = res1; int j; printf("line:%d, station:%d\n", i, n); for( j = n; j >= 2; j--) { i = l[i][j]; printf("line:%d, station:%d\n", i, j-1); }}int main(){ while(scanf("%d", &n) != EOF) { init(); int result = fast_way(); cout << result << endl; print_station(); } return 0;}/*****************************测试数据：P193算法导论（第二版）62 47 82 29 53 13 61 24 43 28 54 14 73 2****************************/