-
Notifications
You must be signed in to change notification settings - Fork 0
/
AssemblyLine.cpp
120 lines (106 loc) · 2.32 KB
/
AssemblyLine.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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
using namespace std;
int min(int x, int y) {
/*
You can use this function
*/
if (x < y) return x;
else return y;
}
void backtracking(int i, int j, int **l) {
if (l[i][j - 1] == 1 && j > 1) {
backtracking(0, j - 1, l);
//cout << j << "th path ";
cout << "1 ";
}
else if (l[i][j - 1] == 2 && j > 1) {
backtracking(1, j - 1, l);
//cout << j << "th path ";
cout << "2 ";
}
else {
cout << "start! ";
}
}
int main() {
int numOfstation;
cin >> numOfstation;
int e1, e2, x1, x2;
int * a1 = new int[numOfstation];
int * a2 = new int[numOfstation];
int * t1 = new int[numOfstation - 1];
int * t2 = new int[numOfstation - 1];
cin >> e1;
for (int i = 0; i < numOfstation; i++)
cin >> a1[i];
cin >> x1;
cin >> e2;
for (int i = 0; i < numOfstation; i++)
cin >> a2[i];
cin >> x2;
for (int i = 0; i < numOfstation - 1; i++)
cin >> t1[i];
for (int i = 0; i < numOfstation - 1; i++)
cin >> t2[i];
/*
Implement here
*/
int **f = new int*[2];
for (int i = 0; i < 2; ++i) {
f[i] = new int[numOfstation];
}
int **l = new int*[2];
for (int i = 0; i < 2; ++i) {
l[i] = new int[numOfstation];
}
f[0][0] = e1 + a1[0];
f[1][0] = e2 + a2[0];
for (int j = 1; j < numOfstation; j++) {
if (f[0][j - 1] + a1[j] <= f[1][j - 1] + t2[j - 1] + a1[j]) {
f[0][j] = f[0][j - 1] + a1[j];
l[0][j] = 1;
}
else {
f[0][j] = f[1][j - 1] + t2[j - 1] + a1[j];
l[0][j] = 2;
}
if (f[1][j - 1] + a2[j] <= f[0][j - 1] + t1[j - 1] + a2[j]) {
f[1][j] = f[1][j - 1] + a2[j];
l[1][j] = 2;
}
else {
f[1][j] = f[0][j - 1] + t1[j - 1] + a2[j];
l[1][j] = 1;
}
}
int optimalF = 0;
int optimalL = 0;
if (f[0][numOfstation - 1] + x1 <= f[1][numOfstation - 1] + x2) {
optimalF = f[0][numOfstation - 1] + x1;
optimalL = 1;
}
else {
optimalF = f[1][numOfstation - 1] + x2;
optimalL = 2;
}
cout << "OptimalF : " << optimalF << endl;
cout << "OptimalL : " << optimalL << endl;
cout << "path Info: " << endl;
for (int j = 1; j < numOfstation; ++j) {
cout << l[0][j] << " ";
}
cout << endl;
for (int j = 1; j < numOfstation; ++j) {
cout << l[1][j] << " ";
}
cout << endl;
// backtracking
cout << "backtracking ... : " << endl;
backtracking(optimalL - 1, numOfstation, l);
cout << optimalL << endl;
delete[] a1;
delete[] a2;
delete[] t1;
delete[] t2;
return 0;
}