做题感悟：这题属于区间DP，开始做事看着和矩阵连乘一样，结果没想出状态转移方程。
解题思路：给木棍添加 一个头一个尾就成为矩阵连乘问题了，从小递推到达最终结果就为dp[ 0 ][ L ] .
状态方程：dp[ i ][ j ] = min { dp [ i ] [ k ] +dp[ k ] [ j ] +d[ j ] - d[ i ] } dp[ i ][ j ] 代表从第 i 处到第 j 处的最优解。
代码：
#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
const int INF = 99999999 ;
using namespace std ;
const int MX = 50 + 10 ;
int L,n ;
int dp[MX][MX],a[MX] ;
void SectionDP()
{
for(int i=0 ;i<=n ;i++)
dp[i][i+1]=0 ;
for(int t=2 ;t<=n ;t++)
for(int i=0 ;i+t<=n ;i++)
{
dp[i][i+t]=INF ;
for(int j=i+1 ;j<i+t ;j++)
dp[i][i+t]=min(dp[i][i+t],dp[i][j]+dp[j][i+t]+a[i+t]-a[i]) ;
}
cout<<"The minimum cutting is "<<dp[0][n]<<"."<<endl ;
}
int main()
{
while(scanf("%d",&L),L)
{
scanf("%d",&n) ;
a[0]=0 ; // 添加尾
for(int i=1 ;i<=n ;i++)
scanf("%d",&a[i]) ;
a[++n]=L ;// 添加头
SectionDP() ;
}
return 0 ;
}