-
Notifications
You must be signed in to change notification settings - Fork 1
/
Tar09.cpp
40 lines (37 loc) · 851 Bytes
/
Tar09.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
#include <iostream>
using namespace std;
const int INF = 100000000;
int main(){
int l, n;
int D[100][100], ci[100];
while (true){
// Se introducen los valores de L y N
cin >> l;
if (l == 0){
break;
}
cin >> n;
// Se guarda en un vector los valores de corte
for (int i = 1; i <= n; i++){
cin >> ci[i];
}
ci[0] = 0;
ci[n + 1] = l;
// Iniciamos la diagonal de la matriz
for (int i = 1; i <= n; i++){
D[i][i] = 0;
}
// Algoritmo de multiplicacion encadenada de matrices
for (int diagonal = 3; diagonal <= n + 2; diagonal++){
for (int i = 0; i <= n + 2 - diagonal; i++){
int j = i + diagonal - 1;
D[i][j] = INF;
for (int k = i; k < j; k++){
D[i][j] = min(D[i][j],D[i][k] + D[k][j] + ci[j] - ci[i]);
}
}
}
cout << "The minimum cutting is "<< D[0][n + 1]<<"."<<endl;
}
return 0;
}