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;
} |
|
