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

CHOP.OUT

说明

第一双 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[],d[],f[][];

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++){

        int x;

        scanf("%d",&x);

        t[x]++;

    }

    k+=;

    if((n>>)<k){

        puts("-1");

        return ;

    }

    for(int i=;i<=;i++)

        for(;t[i];t[i]--)

            d[++d[]]=i;

    memset(f,,sizeof(f));

    f[][]=;

    for(int i=;i<=k;i++)

        for(int j=;j<=d[];j++)

            f[i][j]=dmin(f[i][j],dmin(f[i-][j-]+sq(d[j]-d[j-]),f[i][j-]));

    printf("%d\n",f[k][d[]]);

    return ;

}