GitBook

这里写图片描述 这里写图片描述

刚开始想的是直接排序 然后选取相差最小的就好了 不过发现没这么简单

用到了动态规划思想 也就是“记录结果再利用”

#include<stdio.h>
#include<algorithm>
using namespace std;
int main() {
	int n,k,inf=99999999;
	while(scanf("%d %d",&n,&k)!=EOF) {
		int a[2020];
		int dp[3][2020];
		for(int i=1; i<=n; i++)
			scanf("%d",&a[i]);
		sort(a,a+n);
		for(int i=0; i<3; i++) {
			for(int j=1; j<k+1; j++)
				dp[i][j]=inf;
			dp[i][0]=0;
		}
		sort(a+1,a+n+1);
		for(int i=2; i<=n; i++)
			for(int j=1; j<=k; j++)
				dp[i%3][j]=min(dp[(i-1)%3][j],dp[(i-2)%3][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
		printf("%d\n", dp[n%3][k]);
	}
	return 0;
}
//刚开始想简单了
//直接排序的话
//6 2
//1 8 9 9 10 20
//这样的会出错

题目地址:【杭电】[1421]搬寝室