3618357_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define inf 2100000000

int c, h;
int x[201];
double v[201][201];
double b[201][201][201];

double fabs(double num)
{
	return num > 0 ? num : -num;
}

void init()
{
	int i, j, k;
	double tmp, pos, sum;

	for (i = 0; i <= h; i++)
	{
		for (j = 0; j <= h; j++)
		{
			for (k = 0; k <= h; k++)
			{
				b[i][j][k] = -1;
			}
		}
	}
	for (i = 0; i < h; i++)
	{
		for (j = i + 1; j < h; j++)
		{
			tmp = 1.0 * (x[j] - x[i]) / (j - i);
			pos = x[i];
			sum = 0;
			for (k = i + 1; k < j; k++)
			{
				pos += tmp;
				sum += fabs(pos - x[k]);
			}
			v[i][j] = sum;
		}
	}
}

double solve(int st, int ed, int num)
{
	int i;
	double ans, min, tmp;

	if (ed - st < num)
		return inf;
	if (ed - st == num)
		return 0;
	if (num == 0)
	{
		return v[st][ed];
	}
	if (b[st][ed][num] != -1)
	{
		return b[st][ed][num];
	}
	ans = inf;
	for (i = st + 1; i < ed; i++)
	{
		min = inf;
		for (int n = 0; n < num; n++)
		{
			tmp = solve(st, i, n) + solve(i, ed, num - n - 1);
			if (tmp < min)
			{
				min = tmp;
			}
		}
		if (min < ans)
		{
			ans = min;
		}
	}
	return b[st][ed][num] = ans;
}

int main()
{
	int i;
	int cas;

	scanf("%d", &cas);
	while (cas-- > 0)
	{
		scanf("%d%d", &h, &c);
		for (i = 0; i < h; i++)
		{
			scanf("%d", &x[i]);
		}
		if (c == h)
		{
			puts("0.0000");
			continue;
		}
		init();
		printf("%.4lf\n", solve(0, h - 1, c - 2) / h);
	}
	return 0;
}