3618533_ac_469ms_936k.cc

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

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

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

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

	for (i = 0; i <= h; i++)
	{
		for (j = 0; j <= c; j++)
		{
			b[i][j] = inf;
		}
	}
	b[0][0] = 0;
	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;
				double tt = pos - x[k];
				if (tt < 0)
				{
					tt = -tt;
				}
				sum += tt;
			}
			v[i][j] = sum;
		}
	}
}

void dp()
{
	int i, j, k;

	for (i = 1; i < h; i++)
	{
		for (j = 1; j < c; j++)
		{
			for (k = 0; k < i; k++)
			{
				double tmp = v[k][i] + b[k][j-1];
				if (tmp < b[i][j])
				{
					b[i][j] = tmp;
				}
			}
		}
	}
	printf("%.4lf\n", b[h - 1][c - 1] / h);
}

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();
		dp();
	}
	return 0;
}