搬家

Description

要说我校的搬家史那可有的说的了。就alpha来说，他这个暑假刚经历一次搬寝室。

alpha寝室里的东西有n件，但搬东西真的是件很累的事，他只准备随便搬2*m件就行。

alpha每趟左手、右手分别拎一件物品。

凭借天资聪颖，他迅速地发现了：每搬一趟，他的疲劳度与左、右手的物品的重量差的平方成正比。例如他左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.

他想知道他搬完这2*m件物品后疲劳度最低是多少？

Input

每组输入数据有两行。

第一行有两个数n,m (2*m ≤ n < 2000)。

第二行有n个整数分别表示n件物品的重量(重量是一个小于2¹⁵的正整数)。

0 0表示输入结束。

Output

对于每组输入数据，输出一个正整数，表示他最少的疲劳度，每组输出占一行。

Sample Input

5 1
18467 6334 26500 19169 15724 
7 1
29358 26962 24464 5705 28145 23281 16827 
0 0

Sample Output

492804
1399489

 1 #include<iostream>
 2 #include<cstring>
 3 //#include<fstream>
 4 #include<algorithm>
 5 int a[2050],dp[2050][2050];
 6 using namespace std;
 7 #define inf 0x3f3f3f3f
 8 int main(){
 9     int n,k;
10     //fstream file("haha.txt");
11     while(cin>>n>>k&&n){
12         for(int i=1;i<=n;i++){
13             cin>>a[i];
14         }
15         sort(a+1,a+n+1);
16         memset(dp,0,sizeof(dp));
17         for(int i=1;i<=n;i++){
18             for(int j=1;j<=k;j++){
19                 dp[i][j]=inf;
20             }
21         }
22         for(int i=2;i<=n;i++){
23             for(int j=1;j*2<=i;j++){
24                 dp[i][j]=min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]);
25             }
26         }
27         cout<<dp[n][k]<<endl;
28     }
29     return 0;
30 }

View Code

贪心加动态规划，贪心的思想体现在要将他们排序，排序后，相邻的数的差平方一定比不相邻的小，
然后是动态规划的思想，dp[i][j]表示，从i个物品中拿j对物品的最小值
拿第i个物品的情况是，dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),
不拿第i个物品的情况是，dp[i][j]=dp[i-1][j]