NOJ——1656搬砖（DP）

[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;

}

搬砖

NOJ——1656搬砖（DP）

[1656] 搬砖