隨筆 - 147 
文章 - 71 
trackbacks - 0


           
	

          

          
	
		
          
			
          
	
          
		
          <2009年12月>
          
	
          日一二三四五六
          293012345
          6789101112
          13141516171819
          20212223242526
          272829303112
          3456789
          

          

          
			



			

          常用鏈接
          


          留言簿(1)
          




		
          隨筆分類(146)
          
		
				
			
	
		
          隨筆檔案(147)
          
		
				
			
	
		
          文章分類(28)
          
		
				
			
	
		
          文章檔案(28)
          
		
				
			
	
		
          喜歡的Blog
          
		
				
			
	




          搜索
          

            
	
          • 
		
          •  
	
            • 

          


          最新評論
	
          



          閱讀排行榜
          



          評論排行榜
          


          		
	

          

          
	
					


          
	
	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 飛翔天使 閱讀(280) 評論(0)  編輯  收藏  所屬分類: ACM 
          

          







          
	    
    




          








          

				
	



          



    







          
        
	




主站蜘蛛池模板：
天峻县|
靖边县|
六枝特区|
滨州市|
缙云县|
海原县|
海宁市|
八宿县|
黄浦区|
阳春市|
都兰县|
辽宁省|
巢湖市|
张家港市|
太和县|
景洪市|
腾冲县|
汨罗市|
宾阳县|
中方县|
阳东县|
灯塔市|
新源县|
赤壁市|
江源县|
新津县|
那坡县|
长治县|
盐池县|
嘉善县|
什邡市|
怀宁县|
上思县|
长子县|
滕州市|
芦山县|
博湖县|
和硕县|
交口县|
卢湾区|
潍坊市|