• [1656] 搬砖

  • 时间限制: 2000 ms 内存限制: 65535 K
  • 问题描述
  • 开学了,万恶的大二学长们又要领着大一的鲜肉们一起敲代码搬砖了,这不,著名的杨神拿着n块砖头,当然他把这n块砖头的重量都告诉你了,让你搬走其中的2*k块,其中每次你只能拿2块,消耗的体力是这两块砖头重量之差的平方,比如一块砖重量为5,另一块是11,那么搬走这两块砖头消耗体力为(11- 5)^2 = 36,机智如你,你能算出如何搬2*k块,才能使你花费的体力最小呢?
  • 输入
  • 一个整数t,代表数据组数(t <= 10)
    每组数据包含2个整数n和k,保证0 <= 2*k <= n <= 2000
    接下来一行包含n个整数(每个数都<= 100000)
  • 输出
  • 每组一个整数,代表最小的体力消耗
  • 样例输入
  • 2
    2 1
    1 3
    6 2
    1 4 2 6 11 9
  • 样例输出
  • 4
    5
  • 提示
  • 第二组样例,可以这么搬(1 2) (4 6)组合,或者(1 2) (9 11)组合,这样花费代价是最少的

这题在我看了很久的大神的题解+想了又想之后稍微理解了点,写了下代码......还好过了

让我这个初学者菜鸟神烦的一题...

主要思想:由于平方差最小,那么你sort之后一定是取相邻的一对数字,但是向左或向右就不得而知了,因此要用二位数组记录当前循环到第i件时取了j对所消耗的体力。

两层for是因为每一次可选i件都会对当前的最优解造成影响,但是可以记录在那一次的dp[i]中,因此最后那个dp[n][k]就是可选n件时取k对的最优解

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<sstream>
#include<algorithm>
#include<cmath>
using namespace std;
int zhuan[2010];
int dp[2010][2010];//
int main (void)
{
int t,n,k,i,j,ans;
cin>>t;
while (t--)
{
cin>>n>>k;
memset(zhuan,0,sizeof(zhuan));
memset(dp,0x3f3f3f3f,sizeof(dp));
for (int i=0; i<n; i++)
{
cin>>zhuan[i];
dp[i][0]=0;
}
sort(zhuan,zhuan+n);
for (int i=1; i<=n; i++)//当前循环到的第I件(不一定选)
{
for (int j=1; 2*j<=i&&j<=k; j++)//(当成功入选j件时)
{
dp[i][j]=min(dp[i-2][j-1]+(zhuan[i-2]-zhuan[i-1])*(zhuan[i-2]-zhuan[i-1]) , dp[i-1][j]);//最优决策=min(上一次状态+取i-1与i-2这两件/不取,保持上一件状态)
}
}
cout<<dp[n][k]<<endl;
}
return 0;
}
05-11 16:00