**搬寢室

Time Limit: 2000/1000 MS Memory Limit: 65536/32768 K

Problem Description
搬寢室是很累的,xhd深有體會.時間追述2006年7月9號,那天xhd迫于無奈要從27號樓搬到3號樓,因為10號要封樓了.看著寢室里的n件物品,xhd開始發呆,因為n是一個小于2000的整數,實在是太多了,于是xhd決定隨便搬2k件過去就行了.但還是會很累,因為2k也不小是一個不大于n的整數.幸運的是xhd根據多年的搬東西的經驗發現每搬一次的疲勞度是和左右手的物品的重量差的平方成正比(這里補充一句,xhd每次搬兩件東西,左手一件右手一件).例如xhd左手拿重量為3的物品,右手拿重量為6的物品,則他搬完這次的疲勞度為(6-3)^2 = 9.現在可憐的xhd希望知道搬完這2*k件物品后的最佳狀態是怎樣的(也就是最低的疲勞度),請告訴他吧.

Input
每組輸入數據有兩行,第一行有兩個數n,k(2<=2*k<=n<2000).第二行有n個整數分別表示n件物品的重量(重量是一個小于2^15的正整數).

Output
對應每組輸入數據,輸出數據只有一個表示他的最少的疲勞度,每個一行.

Sample Input
2 1 1 3

Sample Output
4

Author
xhd
解題思路：
題目意思為求n個物品，拿k對使得消耗的體力最少，或者說是這k對物品，每一對中兩件物品的質量差平方最小，所以要使得質量差的平方小，只能排序后取質量相鄰兩個物品作為一對；
現在設dp[i][j]為前i件物品組成k對所消耗的體力最小；
這時分兩種情況含有第i件物品和不含有第i件物品（即第i件物品是不是含在第j對里）
1.含有i件物品 則有 dp[i][j]=dp[i-2][j-1]+(ob[i-1]-ob[i])(ob[i-1]-ob[i])
2.不含第i件物品則有 dp[i][j]=dp[i-1][j]
所以動態轉移方程為 ：dp[i][j]=min(dp[i-2][j-1]+(ob[i-1]-ob[i])(ob[i-1]-ob[i]),dp[i-1][j]);
我們用一組數據來解釋狀態轉移方程。

以最大值0x3f3f3f3f為分界線，為什么要使用0x3f3f3f3f作為最大值，全是個人習慣，在這里用0x7f7f7f7f也可以。但是在有些題目中當兩個無窮大相加的時候進位變為負號，成為極小值，為了避免這種情況出現，用0x3f3f3f3f作為最大值，比無窮大的一半稍小，但是也是一個極大的數，用來做無窮大最好不過。
注 ：

int型是4個字節 一個字節8個位 0x7f7f7f7f 是十六進制 也就是4個0x7f ,一個0x7f 轉化為二進制就是 01111111
因為是int型 第一個位是符號位 ，因而在int 型中 0x7f7f7f7f也就是無窮大的意思。

以無窮大為界限第一階梯代表只要當前值可選就選消耗的體力。

第二階梯代表有一個數據沒有選擇的最優消耗體力，他的選擇機制是選當前兩個，或者跳過去一個，如果跳過這一個比都選要輕松，他會選擇跳過當前值，于是這就是狀態轉移方程，選擇機制是選當前值，或者不選當前值。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; long long int ob[2001]; long long int dp[2001][2001]; const long long int max1=0x3f3f3f3f; int main() {int n,k;while(cin>>n>>k){// memset(dp,max1,sizeof(dp)); memset 最好用來賦值0或-1，不然會出錯。memset(ob,0,sizeof(ob));for(int i=1;i<=n;i++)cin>>ob[i];sort(ob+1,ob+n+1);ob[0]=0;for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){dp[i][j]=max1;}}for(int i=0;i<=n;i++) dp[i][0]=0;for(int i=2;i<=n+1;i++){for(int j=1;j<=k;j++)dp[i][j]=min(dp[i-2][j-1]+(ob[i-1]-ob[i])*(ob[i-1]-ob[i]),dp[i-1][j]);}/* for(int i=0;i<n+1;i++) 遇到不會的題目，就按照他的狀態轉移方程操作后輸出dp數組，來研究狀態轉移方程的實現過程。{for(int j=0;j<n+1;j++){cout<<dp[i][j]<<' ';}cout<<endl;}*/cout<<dp[n][k]<<endl;} }

總結

以上是生活随笔為你收集整理的HDU 1421 搬寝室 解题报告（超详细）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。