52 lines
1.1 KiB
Plaintext
52 lines
1.1 KiB
Plaintext
Dim Shared As Integer U(), V()
|
|
|
|
Sub Aux(i As Integer, j As Integer)
|
|
Dim As Integer k = U(i, j)
|
|
If k < 0 Then
|
|
Print Str(i);
|
|
Else
|
|
Print "(";
|
|
Aux(i, k)
|
|
Print "*";
|
|
Aux(i + k, j - k)
|
|
Print ")";
|
|
End If
|
|
End Sub
|
|
|
|
Sub Optimize(a() As Integer)
|
|
Dim As Integer i, j, k, c
|
|
Dim As Integer n = Ubound(a) - 1
|
|
Redim U(n, n), V(n, n)
|
|
For i = 1 To n
|
|
U(i, 1) = -1
|
|
V(i, 1) = 0
|
|
Next i
|
|
|
|
For j = 2 To n
|
|
For i = 1 To n - j + 1
|
|
V(i, j) = &H7FFFFFFF
|
|
For k = 1 To j - 1
|
|
c = V(i, k) + V(i + k, j - k) + a(i) * a(i + k) * a(i + j)
|
|
If c < V(i, j) Then
|
|
U(i, j) = k
|
|
V(i, j) = c
|
|
End If
|
|
Next k
|
|
Next i
|
|
Next j
|
|
|
|
Print V(1, n); " ";
|
|
Aux(1, n)
|
|
Print
|
|
Erase U, V
|
|
End Sub
|
|
|
|
Dim As Integer A1(1 To 4) = {5, 6, 3, 1}
|
|
Optimize(A1())
|
|
Dim As Integer A2(1 To 13) = {1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}
|
|
Optimize(A2())
|
|
Dim As Integer A3(1 To 12) = {1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}
|
|
Optimize(A3())
|
|
|
|
Sleep
|