UVA - 10003 Cutting Sticks （区间DP）

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int dp[52][52], a[52];
int main(){
	int l, n;
	while(scanf("%d", &l) != EOF){
		if(l == 0) return 0;
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			scanf("%d", &a[i]);
		}
		a[0] = 0;
		a[n + 1] = l;
		memset(dp, 0, sizeof(dp));
		for(int d = 0; d <= n; ++d){
			for(int i = 1; i + d <= n; ++i){
				dp[i][i + d] = 1e9;
				for(int j = i; j <= i + d; ++j){
					dp[i][i + d] = min(dp[i][i + d], dp[i][j - 1] + dp[j + 1][i + d] + a[i + d + 1] - a[i - 1]);
				}
			}
		}
		printf("The minimum cutting is %d.\n", dp[1][n]);
	}
}

/*
题意：
长度1000的木棍，50个切割点需要切割，一次只能切一个，切的代价是切点所在木棍的长度，问切完最少需要多少代价。

思路:
区间dp，dp[i][j]表示[i,j]之间的切点最少需要多少代价切完，然后枚举区间内所有点作为第一个切点，然后转移即可。
注意在两端加一个值辅助转移。
*/