• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

	
            
		

		
		
            
			
					

            
	
	先預處理，把第i個村子到第j個村子中，建一個郵局的最小代價算出來，存在min_cost[i][j]里。
            接下來就可以DP。設f[i][j]為前i個郵局，建在前j個村子的最小代價。那么f[i][j]可以轉移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價是min_cost[j + 1][j + k]。

            

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-9-3 22:18:48
            File Name: pku1160.cpp
            Description: 
            ***********************************************************************            */
            #include             <iostream>
            using namespace std;
            #define out(x) (cout << #x << ": " << x << endl)
            const int maxint = 0x7FFFFFFF;
            typedef             long long int64;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template             <class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
            template             <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

            const int maxn = 310;

            int n, p;

            int min_cost[maxn][maxn];
            int f[maxn][maxn];
            int a[maxn];

            int main()
            {
                scanf(            "%d%d", &n, &p);
                            for (int i = 1; i <= n; i++)
                    scanf(            "%d", &a[i]);
                
                            for (int i = 1; i <= n; i++)
                                for (int j = i; j <= n; j++)
                                {
                        min_cost[i][j]             = 0;
                                    int mid = (i + j) / 2;
                                    for (int k = i; k <= mid; k++)
                            min_cost[i][j]             += a[mid] - a[k];
                                    for (int k = mid + 1; k <= j; k++)
                            min_cost[i][j]             += a[k] - a[mid];
                    }

                            for (int i = 0; i <= p; i++)
                                for (int j = 0; j <= n; j++)
                        f[i][j]             = maxint;
                
                f[            0][0] = 0;
                            for (int i = 0; i <= p; i++)
                                for (int j = 0; j <= n; j++) if (f[i][j] < maxint)
                                {
                                    for (int k = 1; j + k <= n; k++)
                            f[i             + 1][j + k] <?= f[i][j] + min_cost[j + 1][j + k];
                    }
                printf(            "%d\n", f[p][n]);
                            return 0;
            }
            

	
            
		posted on 2007-09-03 22:44 Felicia 閱讀(1526) 評論(3)  編輯 收藏 引用  所屬分類: 動態規劃 
	
            

            
	
	





            
	    
    


            
	
            
		Comments
	
            
		
	
			            
		

            







            






            

				
			
             
            
		
            
		

	
            

            


                
    







            
	   
	



欧美伊香蕉久久综合类网站|
久久精品人妻一区二区三区|
国内精品久久久久久99蜜桃|
久久国产精品99久久久久久老狼|
狠狠色丁香婷婷久久综合不卡|
国产 亚洲 欧美 另类 久久|
久久亚洲日韩看片无码|
亚洲国产精品无码久久久不卡|
热re99久久精品国产99热|
国产精品成人久久久|
欧美一区二区精品久久|
日韩精品久久久久久免费|
久久天天躁狠狠躁夜夜av浪潮|
久久久久亚洲AV片无码下载蜜桃|
青青青青久久精品国产h久久精品五福影院1421|
亚洲女久久久噜噜噜熟女|
国产精品99久久久久久www|
男女久久久国产一区二区三区|
久久一区二区免费播放|
国产福利电影一区二区三区久久老子无码午夜伦不
|
久久精品亚洲一区二区三区浴池|
人妻无码αv中文字幕久久|
日日狠狠久久偷偷色综合免费
|
久久亚洲精品无码播放|
国产成人久久激情91|
精品久久久久久国产潘金莲
|
久久婷婷色综合一区二区|
久久99国产精品尤物|
久久亚洲AV成人无码国产|
久久精品aⅴ无码中文字字幕不卡|
久久久久亚洲AV无码去区首|
亚洲国产精品久久|
中文字幕成人精品久久不卡|
久久久中文字幕|
精品一区二区久久久久久久网站|
日产精品久久久久久久性色|
综合人妻久久一区二区精品|
亚洲精品乱码久久久久久自慰
|
东京热TOKYO综合久久精品|
亚洲精品无码久久久久|
久久99精品久久久久婷婷|