UVa 10003

DP，递推，水题

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxl= 1005;
const int maxn= 55;
const int INF= 0x3f3f3f3f;

int st[maxn];
int dp[maxn][maxn];

void Init(int n)
{
	memset(dp, 0x3f, sizeof(dp));
	for (int i= 0; i<= n; ++i){
		dp[i][i+1]= 0;
	}
}

int main()
{
	int l= 0, n= 0;
	while (1){
		scanf("%d", &l);
		if (0== l){
			break;
		}

		scanf("%d", &n);
		for (int i= 1; i<= n; ++i){
			scanf("%d", st+i);
		}
		st[0]= 0;
		st[n+1]= l;
		Init(n);

		for (int d= 2; d<= n+1 ; ++d){
			for (int i= 0; i+d<= n+1; ++i){
				int x= INF, j= i+d;
				for (int k= 1; k< d; ++k){
					x= min(x, dp[i][i+k]+dp[i+k][j]+st[j]-st[i]);
				}
				dp[i][j]= x;
			}
		}
		printf("The minimum cutting is %d.
", dp[0][n+1]);
	}

	return 0;
}