DreamAngel
如果你希望成功，以恒心為良友，以經驗為參謀，以小心為兄弟，以希望為哨兵。

隨筆 - 147 文章 - 71 trackbacks - 0

2009年12月

>

日

一

二

三

四

五

六

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

我的其它Blog：
www.cppblog.com/dreamangel/
blog.csdn.net/fjnu_angel/

常用鏈接

留言簿(1)

隨筆分類(146)

隨筆檔案(147)

文章分類(28)

文章檔案(28)

喜歡的Blog

搜索

閱讀排行榜

評論排行榜

福建師范大學1772（D）

http://acm.fjnu.edu.cn/show?problem_id=1772

動態規劃：假設前n-1本的取書方案已經解決，單獨考慮第n本的取舍，如果保留第n本增加了已知的不整齊度，則取掉第n本。
首先要按高度進行排序。
dp[i][j] //以i結尾,已取好j本書
初始化：
dp[1][0]=0;
for(i=2;i<=n;i++) dp[i][0]=dp[i-1][0]+Math.abs(w[i]-w[i-1]);
方程：
dp[i][j]=min{dp[i-p-1][j-p]+abs(w[i]-w[i-p-1])}，0<=p<=j，0<=j<=k
ans=min(dp[n-i][k-i)]) ，0<=i<=k

import java.util.*;

import java.io.*;

import java.math.*;

public class ACM_1772{

public static void main(String rgs[]) throws Exception

{

BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

String line = stdin.readLine();

StringTokenizer st = new StringTokenizer(line);

int n = Integer.parseInt(st.nextToken());

int k = Integer.parseInt(st.nextToken());

int i,j,k1,p,tmp;

int[] h = new int[201];

int[] w = new int[201];

for(i=1;i<=n;i++){

line = stdin.readLine();

st = new StringTokenizer(line);

h[i] = Integer.parseInt(st.nextToken());

w[i] = Integer.parseInt(st.nextToken());

}

for(i=1;i<n;i++){

k1=i;

for(j=i+1;j<=n;j++){

if(h[k1]>h[j])

k1=j;

}

if(k1!=i){

tmp=h[k1];

h[k1]=h[i];

h[i]=tmp;

tmp=w[k1];

w[k1]=w[i];

w[i]=tmp;

}

int[][] dp =new int[201][201];

dp[1][0]=0;

for(i=2;i<=n;i++)

dp[i][0]=dp[i-1][0]+Math.abs(w[i]-w[i-1]);

for(i=1;i<=n;i++){

for(j=1;j<=k;j++){

if(j>=i)

break;

dp[i][j]=0xffffff;

if(j==i-1)

dp[i][j]=0;

else{

for(p=0;p<=j;p++){

tmp=dp[i-p-1][j-p];

tmp=tmp+Math.abs(w[i-p-1]-w[i]);

if(tmp<dp[i][j])

dp[i][j]=tmp;

}

int min=dp[n][k];

for(i=1;i<=k;i++){

if(dp[n-i][k-i]<min)

min=dp[n-i][k-i];

}

System.out.println(min);

}

posted on 2009-12-25 20:22 飛翔天使閱讀(275) 評論(0) 編輯收藏所屬分類: ACM

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 福建師范大學1772（D）福建師范大學1908（小丁的試驗）福建師范大學1681（Entropy） ACM中java的使用福建師范大學3008（完美字符串） Contest - FJNU_2009系列賽五(月賽②)解題報告福建師范大學1770（B）福建師范大學1769（A）福建師范大學2009（生日邀請函）福建師范大學2045（小明回家Ⅱ）