• <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 Author:    Leo.W
             3 Descriptipn:    一系列的n件物件,只能搬2*k件,且疲勞度為每次搬得兩件物品的質量差的平方,求最小疲勞度    
             4 How to Do:    DP動態規劃,狀態轉移類似背包問題,先把所有物品排序,再將相鄰物品平方差求出。
             5   */
             6 #include <iostream>
             7 #include <string.h>
             8 #include <algorithm>
             9 using namespace std;
            10 #define min(a,b) (a)<(b)?(a):(b)
            11 int d[2001];
            12 int dp[2002][1001];
            13 int main(){
            14     //freopen("in.txt","r",stdin);
            15     int n,k;
            16     while (scanf("%d%d",&n,&k)!=EOF){
            17         int i,j;
            18         for(i=1;i<=n;i++)    scanf("%d",&d[i]);
            19         sort(d+1,d+n+1);
            20         for(i=1;i<=n-1;i++)    d[i]=(d[i]-d[i+1])*(d[i]-d[i+1]);
            21         memset(dp,127,sizeof(dp));
            22         for(i=0;i<=n;i++)
            23             dp[i][0]=0;
            24         for(i=2;i<=n;i++){
            25             for(j=1;j*2<=i;j++){//關鍵代碼 注意不要重復 所以只能采用二維
            26                 dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+d[i-1]);
            27             }
            28         }
            29         printf("%d\n",dp[n][k]);
            30     }
            31     return 0;
            32 }
            33 
            posted on 2012-03-13 17:44 Leo.W 閱讀(263) 評論(0)  編輯 收藏 引用
            久久精品亚洲一区二区三区浴池| 久久精品国产免费| 欧美激情精品久久久久久久九九九 | 久久乐国产精品亚洲综合| 久久国产成人午夜AV影院| 久久久久99这里有精品10 | 久久91亚洲人成电影网站| 99久久国产免费福利| 99久久精品免费看国产一区二区三区 | 大香伊人久久精品一区二区| 国产情侣久久久久aⅴ免费| 久久久精品日本一区二区三区| 亚洲人成网亚洲欧洲无码久久| 久久精品一区二区三区不卡| 欧美精品丝袜久久久中文字幕| 久久久久免费看成人影片| 无码精品久久一区二区三区 | 久久精品国产亚洲AV高清热 | 亚洲精品无码专区久久同性男| 久久国产色AV免费看| 无码人妻久久一区二区三区蜜桃 | 精品综合久久久久久98| 国产精品美女久久久久| 无遮挡粉嫩小泬久久久久久久 | 精品久久久久久久中文字幕| 久久综合亚洲欧美成人| 香蕉久久AⅤ一区二区三区| 久久AⅤ人妻少妇嫩草影院| 精品久久777| 久久精品国产99国产精品澳门 | 青青草原综合久久大伊人精品| 欧美午夜精品久久久久免费视| 麻豆精品久久久久久久99蜜桃| 久久成人永久免费播放| 久久―日本道色综合久久| 久久99精品国产麻豆| 国产精品久久久久久福利漫画| 精品久久久久久成人AV| 久久99热国产这有精品| 日韩精品国产自在久久现线拍| 欧美精品一本久久男人的天堂|