华师一附中OI组

标题: 筷子 [打印本页]
作者: admin    时间: 2018-6-29 18:17
标题: 筷子
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
作者: 张笑宇    时间: 2018-7-28 08:38
  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. }
复制代码
作者: 黄煦喆    时间: 2018-7-29 09:50
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2