问题 D: 筷子

122 阅读 0 评论 81 点赞

我是靠谱客的博主有魅力未来，这篇文章主要介绍问题 D: 筷子，现在分享给大家，希望可以做个参考。

题目描述

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

输入

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

输出

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

样例输入

10 1

1 1 2 3 3 3 4 6 10 20

样例输出

思路：

这道题是一道动态规划题，首先我们要将所有筷子排序，

这样选定的筷子一定是相邻的，然后就需要用到dp的思想，

我们比较选第i个和第i-1个筷子与不选的区别得到状态转移方程：

b[i][j]=min(b[i-1][j],b[i-2][j-1]+f(a[i],a[i-1]))

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
int f(int x,int y)//求一双筷子的长度差的平方
{
    int m=abs(x-y);
    return m*m;
}
int main()
{
    int n,k;
    cin>>n>>k;
    k=k+3;
    if(n<k*2)//当不能完成k双筷子时输出-1
    {
        cout<<-1;
        return 0;
    }
    int a[10001],b[202][202];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);//先将筷子排序
    for (int i=0;i<=n;i++)//初始化
    {
        b[i][0]=0;
        for(int j=1;j<=k;j++)
        b[i][j]=2e7;
    }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=k;j++)
            b[i][j]=min(b[i-1][j],b[i-2][j-1]+f(a[i],a[i-1]));//状态转移方程
    cout<<b[n][k];
}