• <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>

            pku1948 Triangular Pastures DP+枚舉。海倫公式

            題意
            給出一些木棒,問能否用這些木棒拼成三角形,如果可能求最大的面積。

            解法:
            先給出一個定理:海倫公式

            下面就是枚舉邊長。首先枚舉最長邊c,由于兩邊之和大于第三邊,c的長度必須小于周長的一半,這是一個重要的剪枝。如果還要剪枝,可以先一次DP求得由木棍組合可以達(dá)到的長度。
            確定c以后再枚舉a,然后再次可以用DP驗證木棒能否組合成a、c的長度。這里可以再一次剪枝,枚舉c的時候建議從周長的一半向下枚舉,原因很簡單,盡量構(gòu)造一個較優(yōu)的合法解,根據(jù)海倫公式(p-a)(p-b)(p-c),當(dāng)c確定時最大值的位置也清楚了(b和c相等的位置,如果在最優(yōu)位置(上限,可能達(dá)不到)都不能比最優(yōu)解優(yōu),就直接cut)。然后下面就沒什么難度了。

            代碼:
             1 # include <cstdio>
             2 # include <cstring>
             3 # include <cstdlib>
             4 # include <cmath>
             5 using namespace std;
             6 # include <algorithm>
             7 bool dp[2][855][855];
             8 int plen[1605],pc=0;
             9 int n,len[41];
            10 
            11 int main()
            12 {
            13     int total=0;
            14     scanf("%d",&n);
            15     for(int i=0;i<n;i++)
            16     {
            17       scanf("%d",len+i);
            18       total+=len[i];
            19     }
            20     sort(len,len+n);
            21     bool tmp[1606];
            22     memset(tmp,false,sizeof(tmp));
            23     memset(dp[0],0,sizeof(dp[0]));
            24     dp[0][0][0]=true;
            25     for(int i=1;i<=n;i++)
            26     {
            27       memset(dp[i%2],false,sizeof(dp[i%2]));
            28       for(int j=0;j<=total/2+40;j++)
            29         for(int k=j;k<=total/2+40;k++)
            30            if(j-len[i-1]>=0&&dp[(i-1)%2][min(j-len[i-1],k)][max(j-len[i-1],k)]||
            31               k-len[i-1]>=0&&dp[(i-1)%2][min(j,k-len[i-1])][max(k-len[i-1],j)]||
            32               dp[(i-1)%2][j][k])
            33               dp[i%2][j][k]=true;
            34     }
            35     
            36     tmp[len[0]]=true;
            37     for(int i=1;i<n;i++)
            38       for(int j=0;j<=total;j++)
            39         if(tmp[j]&&j+len[i]<=total)
            40           tmp[j+len[i]]=true;
            41     for(int i=0;i<=total;i++)
            42        if(tmp[i])
            43           plen[pc++]=i;
            44     int best=-1;
            45     for(int c=lower_bound(plen,plen+pc,total/2)-plen-1;c>=0;c--)
            46     {
            47        int a=(total-plen[c])/2,b=total-plen[c]-a;
            48        if(best!=-1&&(total-2*plen[c])*(total-2*a)*(total-2*b)<best) continue;
            49        for(a=0;plen[a]<total-plen[c];a++)
            50          if(plen[c]>=plen[a]&&plen[c]>=total-plen[a]-plen[c]&&dp[n%2][plen[a]][plen[c]]&&(best==-1||best<(total-2*plen[c])*(total-2*plen[a])*(total-2*(total-plen[a]-plen[c]))))
            51              best=(total-2*plen[c])*(total-2*plen[a])*(total-2*(total-plen[a]-plen[c]));
            52     }
            53     if(best==-1) printf("-1\n");
            54     else
            55     {
            56         best=(int)(sqrt(best*(double)total)*25+1e-6);
            57         printf("%d\n",best);
            58     }
            59     //system("pause");
            60     return 0;
            61       
            62 }
            63 

            posted on 2011-02-05 01:02 yzhw 閱讀(294) 評論(0)  編輯 收藏 引用 所屬分類: DPgeometry&phycise

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導(dǎo)航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久综合精品国产一区二区三区| 99久久人人爽亚洲精品美女| 久久精品国产亚洲7777| 精品无码久久久久久尤物| 亚洲精品乱码久久久久久蜜桃不卡| 三级韩国一区久久二区综合| 精品久久久久久无码人妻热| 91久久精品电影| 成人亚洲欧美久久久久| 久久久久久青草大香综合精品| 91久久精品电影| 久久久久久久综合综合狠狠| 日日狠狠久久偷偷色综合96蜜桃| 色天使久久综合网天天| 亚洲精品乱码久久久久久蜜桃| 久久中文字幕无码专区 | 久久久久久精品成人免费图片| 色综合久久中文字幕综合网| 日日狠狠久久偷偷色综合免费| 久久久久亚洲国产| 性欧美丰满熟妇XXXX性久久久| 99久久无码一区人妻a黑| 久久er热视频在这里精品| 99热精品久久只有精品| 日韩精品无码久久一区二区三| 久久久国产打桩机| 国产美女久久精品香蕉69| 国内精品欧美久久精品| 狠狠色丁香婷婷久久综合| 精品久久无码中文字幕| 国产视频久久| 久久久久久伊人高潮影院| 丁香狠狠色婷婷久久综合| 久久免费观看视频| 久久久久亚洲av无码专区| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久综合狠狠综合久久激情 | 国产精品女同一区二区久久| 久久久久久精品无码人妻| 人人狠狠综合久久亚洲婷婷| 伊人色综合久久天天人守人婷|