uva10003（区间dp）

#include<iostream>
#include<string.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[100];int r;
int dp[1003][1003];

int main(){
	int sl;
	while(cin>>sl){
		if(sl==0) break;
	int n;scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//				for(int i=1;i<=n;i++) cout<<a[i];
	memset(dp,inf,sizeof(dp));
	for(int i=0;i<=n;i++) dp[i][i+1]=0;
	a[0]=0;a[n+1]=sl;
	for(int len=2;len<=n+1;len++){
		for(int l=0;l+len<=n+1;l++){
		 r=l+len;
		for(int k=l+1;k<r;k++){
			dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[r]-a[l]);
		}
	}
	}
	cout<<"The minimum cutting is "<<dp[0][n+1]<<"."<<endl;
	}
}

注意边界条件
因为l是从0开始的
r就是len+l<=n+1
而不是len+l-1;
对分割点进行区间dp
一开始以为是对整个stick区间dp，想了好多天。