• <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无码久久不卡| 久久精品免费观看| 久久久久亚洲AV无码专区桃色| 国产精品综合久久第一页| 久久久久亚洲AV无码专区网站| 久久人人青草97香蕉| 国产精品久久久久久吹潮| 伊人丁香狠狠色综合久久| 一本久久a久久精品综合香蕉| 久久亚洲精品成人无码网站| 国产精品美女久久久久久2018| 久久婷婷五月综合成人D啪| 色偷偷88888欧美精品久久久| 国产精品激情综合久久| 99久久国产综合精品女同图片| 免费观看久久精彩视频| 精品国产日韩久久亚洲| 色综合久久综合网观看| 日韩精品久久无码人妻中文字幕| 久久久久国产精品嫩草影院 | 久久精品国产免费| 婷婷久久综合| 996久久国产精品线观看| 性高朝久久久久久久久久| 国内精品久久久久| 久久婷婷国产综合精品| 亚洲欧洲久久久精品| 久久国产精品波多野结衣AV| 久久99中文字幕久久| 麻豆一区二区99久久久久| 99久久这里只精品国产免费| 日本国产精品久久| 99久久精品国产一区二区三区| 国产一区二区精品久久| 久久精品国产亚洲AV忘忧草18| 亚洲国产高清精品线久久| 久久丝袜精品中文字幕| 久久久精品久久久久久| 久久亚洲av无码精品浪潮| 久久久艹| 思思久久99热只有频精品66|