Problem Description
搬寢室是很累的,xhd深有體會(huì).時(shí)間追述2006年7月9號(hào),那天xhd迫于無(wú)奈要從27號(hào)樓搬到3號(hào)樓,因?yàn)?0號(hào)要封樓了.看著寢室里的n件物品,xhd開(kāi)始發(fā)呆,因?yàn)閚是一個(gè)小于2000的整數(shù),實(shí)在是太多了,于是xhd決定隨便搬2k件過(guò)去就行了.但還是會(huì)很累,因?yàn)?k也不小是一個(gè)不大于n的整數(shù).幸運(yùn)的是xhd根據(jù)多年的搬東西的經(jīng)驗(yàn)發(fā)現(xiàn)每搬一次的疲勞度是和左右手的物品的重量差的平方成正比(這里補(bǔ)充一句,xhd每次搬兩件東西,左手一件右手一件).例如xhd左手拿重量為3的物品,右手拿重量為6的物品,則他搬完這次的疲勞度為(6-3)^2 = 9.現(xiàn)在可憐的xhd希望知道搬完這2k件物品后的最佳狀態(tài)是怎樣的(也就是最低的疲勞度),請(qǐng)告訴他吧.
Input
每組輸入數(shù)據(jù)有兩行,第一行有兩個(gè)數(shù)n,k(2<=2k<=n<2000).第二行有n個(gè)整數(shù)分別表示n件物品的重量(重量是一個(gè)小于2^15的正整數(shù)).
Output
對(duì)應(yīng)每組輸入數(shù)據(jù),輸出數(shù)據(jù)只有一個(gè)表示他的最少的疲勞度,每個(gè)一行.
Sample Input
2 1
1 3
Sample Output
4
首先，他要求拿物品的質(zhì)量差的平方，一次拿兩個(gè)，拿就要把數(shù)據(jù)先排序，因?yàn)橹挥羞@樣才能拿到最小的。
dp[i][j]表示i個(gè)數(shù)據(jù)拿j次疲勞度最小。
然后考慮初始化問(wèn)題，就是當(dāng)數(shù)據(jù)只有剛好拿完的時(shí)候，那么結(jié)果就是從前到后兩兩拿最小。表達(dá)式為if(i==2j) {dp[i][j]=dp[i-2][j-1] (a[i]-a[i-1])(a[i]-a[i-1]);}
一般情況，對(duì)于每一個(gè)新物品，都要考慮拿不拿這個(gè)物品，如果拿了。他肯定要和前面一個(gè)湊成對(duì)，前面a[i-1]要確保不能動(dòng)，那么dp[i][j]=dp[i-2][j-1] (a[i]-a[i-1])(a[i]-a[i-1])，如果不拿，那么dp[i][j]=dp[i-1][j]；表示拿前i-1個(gè)數(shù)據(jù)拿j次。
那么狀態(tài)轉(zhuǎn)移方程為：if(i>2j)dp[i][j]=min(dp[i-2][j-1] (a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]);
注意i.和j 的大小關(guān)系。附上代碼：

import java.util.Arrays; import java.util.Scanner; /** 思路：* 排序上升，尋找dp關(guān)系。i=2*j時(shí)。只能等于****/ public class 杭電1421 {public static void main(String[] args){Scanner sc=new Scanner(System.in);while(sc.hasNext()) {int n=sc.nextInt();//n個(gè)數(shù)據(jù)int k=sc.nextInt();//拿K次if(k*2>n||k<1||n<2)break;int a[]=new int[n 1];//物品質(zhì)量int dp[][]=new int[1000][1000];for(int i=1;i<n 1;i ){a[i]=sc.nextInt();}Arrays.sort(a,1,n 1);for(int i=1;i<=n;i ){for(int j=1;j<=k;j ){dp[i][j]=32768;}} for(int i=2;i<=n;i ){for(int j=1;j<=n/2;j ){if(i==2*j) {dp[i][j]=dp[i-2][j-1] (a[i]-a[i-1])*(a[i]-a[i-1]);continue;}else if(i>2*j)dp[i][j]=min(dp[i-2][j-1] (a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]);}}System.out.println(dp[n][k]);}} private static int min(int i, int j) {if(i<j)return i;else return j; } }

總結(jié)

以上是生活随笔為你收集整理的杭电1421java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。