• <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: 博客園 模板提供:滬江博客
            97精品久久天干天天天按摩| 久久99热这里只有精品国产| 亚洲va久久久噜噜噜久久狠狠| 久久人妻AV中文字幕| 亚洲精品无码成人片久久| 青青青青久久精品国产h| 久久久久九九精品影院| 久久久久亚洲AV片无码下载蜜桃 | 99久久精品免费国产大片| 一级a性色生活片久久无| 精品久久一区二区三区| 久久久噜噜噜久久中文字幕色伊伊| 久久亚洲精品人成综合网| 久久亚洲国产精品123区| 久久精品蜜芽亚洲国产AV| 亚洲欧美久久久久9999| 7777久久亚洲中文字幕| 久久综合亚洲色一区二区三区| 久久99精品国产99久久6男男| 久久久久av无码免费网| 国产成人精品久久亚洲高清不卡 | 久久WWW免费人成一看片| 久久国产精品偷99| 久久久久一区二区三区| 亚洲国产精品高清久久久| 国内精品久久久久影院老司| 2021国产成人精品久久| 国产情侣久久久久aⅴ免费| 久久久无码精品亚洲日韩京东传媒 | 狠色狠色狠狠色综合久久| 亚洲人成电影网站久久| 久久久久久无码国产精品中文字幕 | 无码任你躁久久久久久久| 亚洲伊人久久大香线蕉苏妲己| 亚洲中文字幕久久精品无码喷水| 国产精品成人精品久久久| 精品久久久久久久久中文字幕| 欧洲人妻丰满av无码久久不卡 | 日本亚洲色大成网站WWW久久| 99久久精品国产一区二区三区| 久久精品免费一区二区三区|