寻找最经济的木材切割方案

描述

人们需要把一跟很长的木头切成几段，有一家名为 Analog Cutting Machinery (ACM) 的公司正在经营这一业务。他们根据切割前木头的长度来收费，木头越长、收费越高，并且每切割一次就收一次费。

显而易见，在这里切割木头时，不同的切割顺序就会产生不同的价钱。譬如一跟 10 米长的木头，需要在 2、4、7 米处切开。如果顺序在这三个位置切割，需要的费用是 10 + 8 + 6 = 24，因为木头原始长度为 10 米，切掉两米剩 8 米，在四米处切掉剩 6 米。如果按照 4、2、7 的顺序来切割，花费就是 10 + 4 + 6 = 20。

任务

你的老板有很多木材要切割，现在他希望你能够帮他找到最便宜的切割方式。

一次输入可能包含多组数据。每一组数据的第一行是木材的长度L (L<=1000)，如果为 0 则表示输入结束。每组数据的第二行是要切割的次数 N (N<=50)，第三行则是切割的位置Ci(0<Ci<L)。以上数据均为整数。

针对每一组输入，输出切割这段木头的最小费用。

100

3

20 50 75

10

4

4 5 7 8

0 样例输出

200

22

模拟题，动态规划

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

int t,l,n;

while(scanf("%d",&l)!=EOF)

{

if(l==0)

break;

scanf("%d",&n);

int a[n+2];

a[0]=0;

for(int i=1;i<n+1;i++)

scanf("%d",&a[i]);

a[n+1]=l;

int m[n+2][n+2];

for( int w=0;w<=n+1;w++)

{ m[w][w]=0;

m[w][w+1]=0;

m[w][w+2]=a[w+2]-a[w];}

for(int l=3;l<=n+1;l++)

{

for(int i=0;i<=n-l+1;i++)

{ int j=i+l;

m[i][j]=999999999;

for(int k=i;k<=j-1;k++)

{

int q=m[i][k]+m[k][j]+a[j]-a[i];

if(q<=m[i][j])

{ m[i][j]=q;

}

}

}

}

printf("%dn",m[0][n+1]);

}

return 0;

}