• <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>
            posts - 195,  comments - 30,  trackbacks - 0
            After culling his most favorite fruits from the trees in an orchard,Keen AS, a mischievous monkey, is confused of the way in which he can combine these piles of fruits into one in the most laborsaving manner. Each turn he can merely combine any two piles into a larger one. Obviously, by combining N-1 times for N piles of fruits, one pile results eventually. It always takes AS a certain quantity of units of stamina, which equals to the sum of the amounts of fruits in each of the two piles combined, to complete a combination. For instance, given three piles of fruits, containing 1, 2, and 9 fruits respectively, the combination of 1 and 2 would cost 3=1+2 units of stamina, and two piles-3 and 9-are resulted; finally, combining them would cost another 12=3+9 units of stamina, and the total units of stamina taken in the whole procedure is 15=3+12. Surely there are many a possible means to combine these three piles; however, it can be proved that 15 is the minimum amount of units of stamina in demand, and that is what your program is required to do. in this problem ,the fruits are put in a strait line. A pile of fruits 'P' can only combined with the rightest pail on the left of P or the leftest on the right of P, and the united pile will at the position of the bigger one.

            Input

            The input file consists of many test cases. The first line contains an integer N (<=100), indicating the number of piles, and the second line contains N integers, each of which represents the amount of fruits in a pile. no integer will more than 10000, the sequence of integer also means the location of the piles.

            Output

            Your program should print the minimum amount of units of stamina that are required to combine these piles of fruits into one on request.

            Sample Input

            3
            1 2 9
            

            Sample Output

            15
            

            典型的石子合并問題。
            #include<stdio.h>
            int a[101][101],sum[101];
            int stone[101];
            int main()
            {
                int n,i,j,k,flag,l,t;
                while(scanf("%d",&n)!=EOF)
                {
                    for(i=1;i<=n;i++)
                    scanf("%d",&stone[i]);
                    sum[0]=0;
                    for(i=1;i<=n;i++)
                    {
                        sum[i]=sum[i-1]+stone[i];      
                        a[i][i]=0;
                    }
                    for(l=1;l<=n-1;l++)
                    for(i=1;i<=n-l;i++)
                    {
                        flag=0;
                        j=i+l;
                        for(k=i;k<j;k++)                              
                        {
                            t=a[i][k]+a[k+1][j]+sum[j]-sum[i-1];
                            if(!flag)
                            {
                                flag=1;
                                a[i][j]=t;
                            }
                            else if(t<a[i][j])
                            a[i][j]=t;
                        }
                    }
                    printf("%d\n",a[1][n]);
                }
                return 0;
            }
            posted on 2009-06-30 21:01 luis 閱讀(477) 評論(0)  編輯 收藏 引用 所屬分類: 動(dòng)態(tài)規(guī)劃
            <2011年12月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久99精品成人片中文字幕| 久久久久久av无码免费看大片| 久久午夜电影网| 国产精品久久网| 久久99久久成人免费播放| 久久久久国产精品嫩草影院| 久久精品免费一区二区| 久久婷婷国产综合精品| 久久九九久精品国产| 热re99久久6国产精品免费| 国产99久久久国产精免费| 99久久久精品免费观看国产| 狠狠色丁香久久婷婷综合图片 | 精品久久久久久久久中文字幕| 亚洲国产成人精品91久久久| 久久精品免费一区二区三区| 伊人久久成人成综合网222| 日韩影院久久| 青青青伊人色综合久久| 久久综合精品国产二区无码| 中文国产成人精品久久亚洲精品AⅤ无码精品| 亚洲精品乱码久久久久久蜜桃图片| 色综合久久88色综合天天 | 久久精品99久久香蕉国产色戒| 久久婷婷国产综合精品| 久久国产免费| 国产无套内射久久久国产| 久久九九青青国产精品| 91精品国产综合久久婷婷| 久久综合狠狠综合久久| 色综合久久久久久久久五月 | 99精品国产在热久久| 区久久AAA片69亚洲| 2021最新久久久视精品爱 | 久久久久久亚洲Av无码精品专口| 久久性精品| 亚洲国产精品无码久久久秋霞2| 久久精品国产精品亚洲下载| 国产精品va久久久久久久| 久久婷婷色综合一区二区| 四虎影视久久久免费观看|