HDU 1421 搬寝室(dp)

• 1.含有i件物品 则有      f[i][j]=f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]);
• 2.不含第i件物品则有   f[i][j]=f[i-1][j];

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define CLR(a) memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
const double eps=1e-6;
const int INF = 0x3f3f3f3f;
const int maxn=2e3+10;
int w[maxn];
int dp[maxn][maxn];

int main() {
	int n,k;
	while(scanf("%d%d", &n,&k)!=EOF) {
		rep(i,1,n) scanf("%d", &w[i]);
		sort(w+1,w+n+1);
		memset(dp,INF,sizeof(dp));
		rep(i,0,n)dp[i][0]=0;
		rep(i,2,n) {
			rep(j,1,i/2) {
				dp[i][j] = min(dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]),dp[i-1][j]);
			}
		}
		cout<<dp[n][k]<<endl;
	}
	return 0;
}