福建师范大学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 飞翔天使阅读(264) 评论(0) 编辑收藏所属分类: ACM

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

最新评论

阅读排行榜

评论排行榜


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理
相关文章: 福建师范大学1772（D）福建师范大学1908（小丁的试验）福建师范大学1681（Entropy） ACM中java的使用福建师范大学3008（完美字符串） Contest - FJNU_2009系列赛五(月赛②)解题报告福建师范大学1770（B）福建师范大学1769（A）福建师范大学2009（生日邀请函）福建师范大学2045（小明回家Ⅱ）