// UVa 10003 - Cutting Sticks #include <iostream> #include <string.h> #include <limits.h> using namespace std; #define oo INT_MAX int main() { int l; cin >> l; while (l) { int n, cut[51], T[51][51]; cin >> n; for (int i = 1; i <= n; i++) cin >> cut[i]; cut[0] = 0; cut[++n] = l; for (int j = 1; j <= n; j++) for (int i = j - 1; i >= 0; i--) { if (i + 1 == j) T[i][j] = 0; else { T[i][j] = oo; for (int k = i + 1; k < j; k++) { if (T[i][k] + T[k][j] < T[i][j]) T[i][j] = T[i][k] + T[k][j]; } T[i][j] += cut[j] - cut[i]; } } cout << "The minimum cutting is " << T[0][n] << "." << endl; cin >> l; } return 0; }
Saturday, June 13, 2015
UVa 10003 - Cutting Sticks
Subscribe to:
Post Comments (Atom)
What line 27 code does "T[i][j] = oo;"?
ReplyDeleteIt sets T[i][j] to very big number. I defined oo as INT_MAX.
Deletewhat is the name of classic dp you use ???
ReplyDeleteMaybe there's another algorithm more similar but it reminds me of a Floyd-Warshall. The loops are like saying from i to j using k between them.
Delete