1672.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1672 on 2005-12-25 at 01:28:44 */ 
#include <cstdio>

const int MAX = 256;
const int INF = 2000000000;

int main()
{
	int cost[MAX][MAX], p[MAX], q[MAX];
	int sum[MAX], bp[MAX][MAX];
	int n, i, j, k;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 1; i <= n; i++) {
			scanf("%d", &p[i]);
		}
		for(i = 0; i <= n; i++) {
			scanf("%d", &q[i]);
		}
		sum[0] = q[0];
		bp[0][0] = cost[0][0] = 0;
		for(i = 1; i <= n; i++) {
			sum[i] = sum[i-1] + p[i] + q[i];
			cost[i][i] = 0;
			bp[i][i] = i;
		}
		for(k = 1; k <= n; k++) {
			for(i = 0; i+k <= n; i++) {
				int m = i + k;
				cost[i][m] = INF;
				for(j = bp[i][m-1]; j <= bp[i+1][m]; j++) {
					if(cost[i][m] > cost[i][j] + cost[j+1][m]) {
						cost[i][m] = cost[i][j] + cost[j+1][m];
						bp[i][m] = j;
					}
				}
				cost[i][m] += sum[m] - sum[i] + q[i];
			}
		}
		printf("%d\n", cost[0][n]);
	}
	
	return 0;
}