1421.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 49 行

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int obj[2010];
int dp[2010][1010];
int n, k;

int cmp(const void *p, const void *q)
{
    return (*(int *)p - *(int *)q);
}

int main()
{
	int i, j;
	while (scanf("%d %d", &n, &k) == 2)
	{
		memset(dp, 0, sizeof(dp));

		for (i = 1; i <= n; i++)
		{
			scanf("%d", &obj[i]);
		}

		qsort(obj + 1, n, sizeof(long), cmp);

		for (i = 1; i <= k; i++)
		{
			for (j = 1; j <= i; j ++)
			{
				dp[2 * i][i] += (obj[2 * j] - obj[2 * j - 1]) * (obj[2 * j] - obj[2 * j - 1]);
			}
			for (j = 2 * i + 1; j <= n; j++)
			{
				int t = dp[j - 2][i - 1] + (obj[j] - obj[j - 1]) * (obj[j] - obj[j - 1]);

				if (t > dp[j - 1][i])
				{
					t = dp[j - 1][i];
				}
				dp[j][i] = t;
			}
		}

		printf("%d\n", dp[n][k]);
	}
	return 0;
}