1738.cpp

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

/* This Code is Submitted by wywcgs for Problem 1738 on 2006-10-01 at 21:51:05 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 256;
const int INF = 1 << 30;

int main()
{
	double f;
	int n, w[N], cost[N][N], sum[N][N];
	
	while(scanf("%d %lf", &n, &f) != EOF && n != 0) {
		for(int i = 0; i < n; i++) scanf("%d", &w[i]);
		for(int i = 0; i < n; i++) { sum[i][i] = w[i]; cost[i][i] = 0; }
		for(int j = 1; j < n; j++)
			for(int i = 0; i < n; i++) {
				int p = (i+j)%n;
				sum[i][p] = sum[i][(p+n-1)%n]+w[p];
				cost[i][p] = INF;
				for(int k = i; k != p; k = (k+1)%n)
					cost[i][p] <?= cost[i][k]+cost[(k+1)%n][p]+max(sum[i][k], sum[(k+1)%n][p]);
			}
		int best = INF;
		for(int i = 0; i < n; i++) best <?= cost[i][(i+n-1)%n];
		printf("%.2lf\n", f*best);
	}
	
	return 0;
}