UVA 10003 切木棍 Cutting Sticks

本文主要是介绍UVA 10003 切木棍 Cutting Sticks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

切木棍 Cutting Sticks

题面翻译

翻译

有一根长度为L（L＜1000）的棍子，还有n（n＜50）个切割点的位置（按照从小到大排列）。你的任务是在这些切割点的位置处把棍子切成n＋1部分，使得总切割费用最小。每次切割的费用等于被切割的木棍长度。例如，L=10，切割点为2, 4, 7。如果按照2, 4, 7的顺序，费用为10＋8＋6=24，如果按照4, 2, 7的顺序，费用为10＋4＋6=20。

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

The minimum cutting is 200.
The minimum cutting is 22.

分析：

把整个木棍放到数轴上，左右端点以及切割点就成为了数轴上的点。
设木棍最左端点 a[0]=0，最右端点 a[n+1]=L，a[1] ~ a[n] 是各切割点坐标。则切割一次 x ~ y 费用是 a[y]-a[x] 。
每一段木棍，我们只需枚举它的切割点，取费用最小的就可以啦。

代码：

#include<bits/stdc++.h>using namespace std;int L,n;int a[110];
int b[110][110];int dfs(int x,int y)
{if(b[x][y]!=-1) {return b[x][y];}if(x+1==y)        {return b[x][y]=0; }int sum=100000;for(int i=x+1;i<y;i++)      {sum=min(sum,dfs(x,i)+dfs(i,y));}return b[x][y]=sum+(a[y]-a[x]);  
}int main()
{while(cin>>L){memset(b,-1,sizeof(b));if(L==0) {break; }cin>>n;	for(int i=1;i<=n;i++) {cin>>a[i]; a[n+1]=L;}int k=dfs(0,n+1);printf("The minimum cutting is %d.\n",k);}return 0;
}