# boards

JobHunting版 - 请教四边形不等式

Senior Electrical Design Engineer请教一道数学题

 进入JobHunting版参与讨论
 1 (共1页)
 l*********y发帖数: 142 1我在做 uva 10003, 题目如下， You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work requires that they only make one cut at a time. It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 b ecause the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price. Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick. 记忆化搜索是n^3, 听说四边形不等式可以加速到n^2, 请问谁能给指出下面的DP应该如何 改？ 多谢了！ #include using namespace std; int cut[51]; int cost[51][51]; void Init() { for (int i = 0; i < 51; i++) { fill_n(cost[i], 51, numeric_limits::max() / 10); } } int DP(int i, int j) { if (i == j - 1) { return 0; } else if (cost[i][j] != numeric_limits::max() / 10) { return cost[i][j]; } else { for (int k = i + 1; k < j; k++) { int tmp = DP(i, k) + DP(k, j) + cut[j] - cut[i]; if (tmp < cost[i][j]) { cost[i][j] = tmp; } } return cost[i][j]; } } int main() { int length; while (cin >> length) { if (length == 0) break; int numofcut; cin >> numofcut; Init(); fill_n(cut, 51, 0); cut[0] = 0; for (int i = 1; i <= numofcut; i++) { cin >> cut[i]; } cut[numofcut + 1] = length; int cost = DP(0, numofcut + 1); cout << "The minimum cutting is " << cost << "." << endl; } return 0; }
 1 (共1页)
 进入JobHunting版参与讨论

OPT CA center case收到yahoo口头offer, 求选择问题！！！

Senior Electrical Design Engineer请教一道数学题