• <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>
            隨筆-65  評論-6  文章-0  trackbacks-0
             1 //還是轉移方程搞懂了就沒問題 
             2 #include <iostream>
             3 using namespace std;
             4 #define MaxSize 205
             5 #define inf 0x7ffffff
             6 int f[MaxSize],dp[33][MaxSize],cost[MaxSize][MaxSize] ;
             7 //餐館位置、前j個餐館設立i個倉庫的最短距離、第i個餐館到第j個餐館的設立一個倉庫的最短距離
             8 inline int abs(int a){
             9     if(a<0)    a=-a;
            10     return a;
            11 }
            12 inline int min(int a,int b){
            13     return a<b?a:b;
            14 }
            15 int main(){
            16     //freopen("in.txt","r",stdin);
            17     int i,j,w,n,k,no=0;
            18     while (scanf("%d %d",&n,&k),(n||k)){
            19         for(i=1;i<=n;i++)
            20             scanf("%d",&f[i]);
            21         for(i=1;i<=n;i++)
            22             for(j=i;j<=n;j++){
            23                 int pos=(i+j)>>1,temp1=0;
            24                 for(w=i;w<=j;w++)
            25                     temp1+=abs(f[w]-f[pos]);
            26                 if(pos&1){
            27                     int temp2=0;            
            28                     for(w=i;w<=j;w++)
            29                         temp2+=abs(f[w]-f[pos+1]);
            30                     cost[i][j]=min(temp1,temp2);
            31                 }
            32                 else
            33                     cost[i][j]=temp1;
            34             }
            35         memset(dp,0,sizeof(dp));
            36         for(i=1;i<=n;i++)
            37             dp[1][i]=cost[1][i];
            38         for(i=2;i<=k;i++)
            39             for(j=i;j<=n;j++){
            40                 dp[i][j]=inf;
            41                 for(w=i-1;w<j;w++)
            42                     dp[i][j]=min(dp[i][j],dp[i-1][w]+cost[w+1][j]);
            43             }
            44                 
            45         printf("Chain %d\n",++no);
            46         printf("Total distance sum = %d\n\n",dp[k][n]);
            47     }
            48     return 0;
            49 }
            posted on 2012-07-11 11:10 Leo.W 閱讀(357) 評論(0)  編輯 收藏 引用
            av无码久久久久不卡免费网站| 91久久九九无码成人网站| 婷婷久久综合九色综合绿巨人 | 亚洲性久久久影院| 免费精品国产日韩热久久| 久久久无码精品亚洲日韩蜜臀浪潮| 99久久久精品| 亚洲精品午夜国产va久久| 国产精品久久影院| 亚洲国产成人久久精品99 | 青青国产成人久久91网| 久久影院午夜理论片无码| 伊人久久精品无码二区麻豆| 久久99精品国产一区二区三区| 久久综合九色欧美综合狠狠| 久久国产免费观看精品3| 亚洲七七久久精品中文国产| 久久久国产精品网站| 久久久久亚洲AV成人网人人网站| 97久久精品人人澡人人爽| 久久99国产精品尤物| 中文字幕无码久久人妻| 2021国产成人精品久久| 久久夜色精品国产噜噜亚洲AV| 青青草原综合久久大伊人导航| 九九久久99综合一区二区| 日产精品99久久久久久| 亚洲国产成人精品久久久国产成人一区二区三区综 | 欧美亚洲国产精品久久| 精品久久久久中文字| 久久精品无码一区二区三区| 亚洲国产精品无码久久一线| 一本大道久久香蕉成人网| 久久99精品九九九久久婷婷| 99久久99久久| 潮喷大喷水系列无码久久精品| 久久久国产亚洲精品| 久久这里只精品99re66| 少妇人妻综合久久中文字幕| 久久亚洲色一区二区三区| 久久久久亚洲AV成人网|