noj[1581] 筷子

题目描述

A先生有很多双筷子。确切的说应该是很多根，因为筷子的长度不一，很难判断出哪两根是一双的。这天，A先生家里来了K个客人，A先生留下他们吃晚饭。加上A先生，A夫人和他们的孩子小A，共K+3个人。每人需要用一双筷子。A先生只好清理了一下筷子，共N根，长度为T1,T2,T3,……,TN.现在他想用这些筷子组合成K+3双，f使每双的筷子长度差的平方和最小。(怎么不是和最小？？这要去问A先生了，呵呵)

输入

输入文件共有两行，第一行为两个用空格隔开的整数，表示N,K(1≤N≤100, 0<K<50)，第二行共有N个用空格隔开的整数，为Ti.每个整数为1～50之间的数。

输出

输出文件仅一行。如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。

样例

CHOP.IN

10 1
1 1 2 3 3 3 4 6 10 20

CHOP.OUT

5

说明

第一双 1 1

第二双 2 3

第三双 3 3

第四双 4 6

(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5

题解

先判断是否能凑齐k+3双筷子。

把n双筷子排序后，相邻的筷子一定排在一起。

那么，设f[i][j]表示1~j根筷子组成i双的最小平方差之和

再把问题分为取和不取两种情况，

1）继承前1~j-1根筷子组成i双的最小平方差之和

2）从1~j-1根筷子组成i-1双的最小平方差之和来推导

因此，状态转移方程为：

f[i][j]=min{f[i][j-1],f[i-1][j-2]+(len[j]-len[j-1])*(len[j]-len[j-1])}

#include<stdio.h>
#include<memory.h>
#define sq(x) ((x)*(x))
#define dmin(a,b) ((a)<(b)?(a):(b))
using namespace std;
bool flag;
int n,k,t[51],d[101],f[51][101];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        t[x]++;
    }
    k+=3;
    if((n>>1)<k){
        puts("-1");
        return 0;
    }
    for(int i=1;i<=50;i++)
        for(;t[i];t[i]--)
            d[++d[0]]=i;
    memset(f,60,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=k;i++)
        for(int j=2;j<=d[0];j++)
            f[i][j]=dmin(f[i][j],dmin(f[i-1][j-2]+sq(d[j]-d[j-1]),f[i][j-1]));
    printf("%d
",f[k][d[0]]);
    return 0;
}