Description
你的任务是替一家叫Analog Cutting Machinery (ACM)的公司切割木棍。切割木棍的成本是根据木棍的长度而定。而且切割木棍的时候每次只切一段。很显然的，不同切割的顺序会有不同的成本。
例如：有一根长10公尺的木棍必须在第2、4、7公尺的地方切割。这个时候就有几种选择了。你可以选择先切2公尺的地方，然后切4公尺的地方，最后切7公尺的地方。这样的选择其成本为：10+8+6=24。因为第一次切时木棍长10公尺，第二次切时木棍长8公尺，第三次切时木棍长6公尺。但是如果你选择先切4公尺的地方，然后切2公尺的地方，最后切7公尺的地方，其成本为：10+4+6=20，这成本就是一个较好的选择。
你的老板相信你的电脑能力一定可以找出切割一木棍所需最小的成本。
Format
Input
第一行一个整数L(L<1000)表示木棒的长度，第二行一个整数n(n <= 50),第三行n个数表示切割的的位置(位置严格单调递增)。
Output
输出一行一个整数，表示最小的成本。
Samples
输入数据 1
10
4
4 5 7 8
输出数据 1
22
数据范围与约定
30% n<=10,L<1000
100% n<=50, L<1000
//思路:把每个木棍分成已经切割好的状态，在从切割好进行复原，
//复原过程中用区间dp的方法记录花费
#include <bits/stdc++.h>
using namespace std;
int l,n;
int f[60],dp[60][60];
int main()
{
cin>>l>>n;
int tmp=0,x;
for(int i=1;i<=n;i++)
{
cin>>x;
//f[i]内存的是第i段的长度
f[i]=x-tmp;
tmp=x;
}
f[n+1]=l-x;//右边界f[n+1]是木棍的总长度,所以dp[1][n+1]就是复原成总长度需要花费的最小价值
for(int num=1;num<n+1;num++)
{
for(int i=1;i<=n-num+1;i++)//切割起点
{
int j=i+num;//切割终点
int minn=2147483647,sum=0;//sum为当前要复原的长度
//计算sum
for(int k=i;k<=j;k++)
{
sum+=f[k];
}
for(int k=i;k<j;k++)
{
//dp[i][k]为复原[i,k]段所需要的最小价值
//dp[k+1][j]为复原[k+1,j]段所需要的最小价值
//为什么一定要加上当前要复原的长度
//才是复原[i,j]区间所需要的最小价值
minn=min(minn,dp[i][k]+dp[k+1][j]+sum);
}
dp[i][j]=minn;//更新dp[i][j]
}
}
cout<<dp[1][n+1];
return 0;
}