题目大意：

一个长为L的棍子，有n个切分点，切割费用=被切割时木棍的长度，求最小的切割费用

分析：

区间$dp$。$dp[i][j]=[i,j]$区间的最小切割费用。状态转移方程$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[j]-a[i]),a[i]$为每个切分点的位置。需要注意的是初始状态$dp[i][i+1]$就已经不能在被分割了所以要重置成$0$，$a[0]=0,a[n+1]=l$表示两个端点。

code:

#define debug
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7;
const int MAXN = 5e3 + 10;
const ll INF = 0x3f3f3f3f;
const ll inf = 0x7fffff;
const ll mod = 1e9 + 7;
const int MOD = 10007;
int a[maxn];
int dp[MAXN][MAXN];
void solve() {
	int l,n;
	while(~scanf("%d",&l)&&l){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		a[n+1]=l;
		memset(dp,INF,sizeof(dp));
		for(int i=0;i<=n;i++)dp[i][i+1]=0;
		for(int k=2;k<=n+1;k++){
			for(int i=0;i+k<=n+1;i++){
				for(int j=i;j<i+k;j++){
					dp[i][i+k]=min(dp[i][i+k],dp[i][j]+dp[j][i+k]+a[i+k]-a[i]);
				}
			}
		}
		printf("The minimum cutting is %d.\n",dp[0][n+1]);
	}
}
int main(int argc, char const *argv[]) {
//  ios_base::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
#ifdef debug
  freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
  int T=1;
//	cin>>T;
  while(T--)
    solve();
  return 0;
}