筷子

admin

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，否则输出长度差平方和的最小值。

样例
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

张笑宇

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstring>
   
4. using namespace std;
   
5. const int mx=110;
   
6. int n,k,a[mx];
   
7. int dp[mx][mx],s[mx][mx];///dp[i][j]表示从前i只筷子中的最小值
   
8. int main()///s[i][j]表示i和j的平方差
   
9. {
   
10.     cin>>n>>k;
    
11.     for (int i=1; i<=n; i++) cin>>a[i];
    
12.     sort(a+1,a+n+1);///排序,使两只筷子之间的距离最小
    
13.     k=k+3;
    
14.     if (2*k>n) {cout<<"-1";return 0;}
    
15.     for (int i=1; i<=n; i++)
    
16.         for (int j=1; j<=n; j++)
    
17.             s[i][j]=(a[i]-a[j])*(a[i]-a[j]);
    
18.     memset(dp,127/3,sizeof(dp));///全部赋值为最大
    
19.     for (int i=0;i<=n;i++) dp[i][0]=0;
    
20.     for (int i=2; i<=n; i++)
    
21.         for (int j=1; j<=k; j++)
    
22.             dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i-1][i]);
    
23.     cout<<dp[n][k];///用或不用第i只木棍
    
24.     return 0;
    
25. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,k,l[101],s[101],dp[101][101];
   
5. int main()
   
6. {
   
7.     cin>>n>>k;
   
8.     k+=3;
   
9.     if((k<<1)>n)cout<<-1;
   
10.     else
    
11.     {
    
12.         for(int i=1;i<=n;i++)cin>>l[i];
    
13.         sort(l+1,l+n+1);
    
14.         for(int i=1;i<=n;i++)
    
15.             for(int j=1;j<=k;j++)dp[i][j]=99999999;
    
16.         for(int i=1;i<=n;i++)s[i]=(l[i]-l[i-1])*(l[i]-l[i-1]);
    
17.         for(int i=1;i<=n;i++)
    
18.             for(int j=1;j<=k;j++)
    
19.                 if((j<<1)>i)continue;
    
20.             else dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+s[i]);
    
21.         cout<<dp[n][k];
    
22.     }
    
23.     return 0;
    
24. }
    

复制代码