题目大意：

一个长为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 
     
      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
      
       >T;  while(T--)    solve();  return 0;}