首页 > 代码库 > UVa 10003 (可用四边形不等式优化) Cutting Sticks
UVa 10003 (可用四边形不等式优化) Cutting Sticks
题意：
有一个长为L的木棍，木棍中间有n个切点。每次切割的费用为当前木棍的长度。求切割木棍的最小费用。
分析：
d(i, j)表示切割第i个切点到第j个切点这段所需的最小费用。则有d(i, j) = min{d(i, k) + d(k, j)} + a[j] - a[i]; ( i < k < j ) 最后一项是第一刀的费用。
时间复杂度为O(n3)
最后还要注意一下输出格式中整数后面还要加一个句点。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 1000000000; 8 const int maxn = 60; 9 int a[maxn], L, n, d[maxn][maxn];10 11 int main(void)12 {13 #ifdef LOCAL14 freopen("10003in.txt", "r", stdin);15 #endif16 17 while(scanf("%d", &L) == 1 && L)18 {19 scanf("%d", &n);20 for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);21 a[0] = 0, a[++n] = L;22 //for(int i = 0; i < n; ++i) d[i][i+1] = a[i+1] - a[i];23 24 for(int l = 2; l <= n; ++l)25 for(int i = 0; i + l <= n; ++i)26 {27 d[i][i+l] = INF;28 for(int k = i + 1; k < i + l; ++k)29 d[i][i+l] = min(d[i][k] + d[k][i+l] + a[i+l] - a[i], d[i][i+l]);30 }31 32 printf("The minimum cutting is %d\n", d[0][n]);33 }34 35 return 0;36 }
可以用四边形不等式来优化到O(n2)，待续……
UVa 10003 (可用四边形不等式优化) Cutting Sticks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。