原題傳送門

題目描述

叉燒的生日快到了，他決定邀請K-1個朋友來他家吃飯，加上叉燒一共有K個人。
叉燒有N根筷子，這些筷子很奇特，長短不一。現在叉燒需要整理出K雙筷子，使每雙筷子長度差的平方和最小。

輸入格式

第一行為兩個用空格隔開的整數N,K(1≤N≤100, 0≤K≤50)，表示有N根筷子，K個人。
第二行共有N個用空格隔開的整數為Ti，表示每根筷子的長度。1≤Ti≤50

輸出格式

如果湊不齊K雙筷子，輸出-1，否則輸出一個整數，代表使每雙筷子長度差的平方和。

樣例輸入

4 1
1 3 6 10

樣例輸出

4

說點啥

這道題難度有點大，至少對我如此，難點在于找到動態規劃的i和j分別代表什么才能表示出每個狀態，找到這個之后就比較簡單了，比賽當時我沒找到，賽后才靈光一現反應過來。

先排序，然后i表示已湊集幾雙筷子，j表示處理到第幾雙筷子，剩下就很簡單，大家都明白了

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,k,t[105],c[105],dp[55][105],Max=99999999;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>t[i];
	
	sort(t+1,t+n+1);
	for(int i=2;i<=n;i++)
		c[i]=(t[i]-t[i-1])*(t[i]-t[i-1]);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=i*2-1;j++)
			dp[i][j]=Max;
	
	for(int i=1;i<=k;i++)
		for(int j=1;j<=n;j++)
			if(dp[i][j]!=Max)
				dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+c[j]);
				
	if(dp[k][n]==Max)
		cout<<"-1"<<endl;
	else
		cout<<dp[k][n]<<endl;
	return 0;
}