• <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>
            syhd142  
            日歷
            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011
            統(tǒng)計
            • 隨筆 - 23
            • 文章 - 122
            • 評論 - 31
            • 引用 - 0

            導(dǎo)航

            常用鏈接

            留言簿(2)

            隨筆檔案(23)

            文章分類(270)

            文章檔案(122)

            我的豆瓣

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

             
            題意:從一個非遞減序列中找出k個3元組(x,y,z),其中x<=y<=z,一個三元組的代價是(x-y)^2,要求這k個三元組的代價和最小。
            解法:DP,令a[i][j]表示從前i個數(shù)中選擇j個3元組,那么轉(zhuǎn)移方程為:a[i][j] = min(a[i-1][j],a[i-2][j-1]+w(l[i],l[i-1]));很好理解,如果使用l[i],那么肯定要和l[i-1]一起使用(因為序列是非遞減的,可以證明),所以就有了第二個轉(zhuǎn)移方程,如果不適用l[i]那么它就和i-1個數(shù)種選擇j個三元組的結(jié)果一樣,注意當(dāng)3*j>i時無效。
            還有一點需要注意的就是如何選取z確保z>=x>=y,看了人家的提示才知道,把數(shù)組從到小排列,這樣就不需要考慮z的影響了。從發(fā)覺自己還沒有領(lǐng)悟DP,狀態(tài)設(shè)計還需要看人家的思路才能寫出來,o(╯□╰)o
            #include <stdio.h>
            #include 
            <string.h>
            #include 
            <algorithm>

            #define N 5005
            #define MIN(a, b) (a < b ? a : b)

            int l[N], w[N], a[N][1010];

            int cmp(int a, int b)
            {
                
            return a > b;
            }

            int main()
            {
                
            int t, k, n;
                scanf(
            "%d"&t);
                
            while(t--)
                {
                    scanf(
            "%d %d"&k, &n);
                    k 
            += 8;
                    
            for(int i = 1; i <= n; i++)
                        scanf(
            "%d"&l[i]);
                    
                    std::sort(l 
            + 1, l + n + 1, cmp);
                
            //    for(int i = 1; i <= n; i++) printf("%4d", l[i]);
                
            //    printf("\n");
                    
                    
            for(int i = 2; i <= n; i++)
                        w[i] 
            = (l[i] - l[i - 1]) * (l[i] - l[i - 1]);
                    
                    memset(a, 
            127sizeof(a));
                    
            for(int i = 0; i <= n; i++) a[i][0= 0;
                     
                    
            for(int i = 3; i <= n; i++)
                    {
                        
            for(int j = 1; j <= k && 3 * j <= i; j++)
                        {
                            a[i][j] 
            = MIN(a[i - 1][j], a[i - 2][j - 1+ w[i]);
                        }
                    }
                    printf(
            "%d\n", a[n][k]);
                }
                
            return 0;
            }
            posted on 2010-06-19 12:14 Fucker 閱讀(322) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPCDP
             
            Copyright © Fucker Powered by: 博客園 模板提供:滬江博客
            久久精品国产一区二区| 欧洲国产伦久久久久久久| 精品无码久久久久久尤物| 欧美大香线蕉线伊人久久| 91精品国产综合久久精品| 久久久精品一区二区三区| 精品熟女少妇aⅴ免费久久| 中文字幕无码久久精品青草| 奇米影视7777久久精品| 精品蜜臀久久久久99网站| 久久久久亚洲AV成人网人人网站| 久久成人小视频| 色偷偷888欧美精品久久久| 亚洲国产精品无码久久九九| 久久国产精品无码HDAV| 久久这里有精品视频| 久久精品无码午夜福利理论片| 久久久久97国产精华液好用吗| 一本一本久久aa综合精品| 国内精品久久久久久久影视麻豆 | 亚洲狠狠婷婷综合久久久久| 久久99毛片免费观看不卡| 色天使久久综合网天天| 久久er国产精品免费观看8| 亚洲AV无码一区东京热久久| 久久精品这里只有精99品| 国产国产成人精品久久| 久久精品国产乱子伦| 久久精品国产WWW456C0M| 9久久9久久精品| 久久久久亚洲精品天堂| 亚洲国产欧洲综合997久久| 国内精品久久久久影院网站| 久久久久久狠狠丁香| 久久久久亚洲AV无码专区体验| 麻豆av久久av盛宴av| 亚洲日本久久久午夜精品| 久久国产V一级毛多内射| 久久久精品国产Sm最大网站| 久久国产午夜精品一区二区三区| 国产亚洲色婷婷久久99精品91|