• <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)  編輯 收藏 引用 所屬分類: 動態規劃
            <2011年4月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久亚洲国产精品123区| 亚洲精品乱码久久久久久| 色综合久久最新中文字幕| 久久精品18| 国产偷久久久精品专区| 久久99精品国产一区二区三区| 久久99热这里只有精品国产| 国产毛片欧美毛片久久久| 久久精品国产一区| 国内精品人妻无码久久久影院导航 | 欧美一区二区精品久久| 一级做a爰片久久毛片看看| 国产精品久久久久aaaa| 久久久久无码精品| 国内精品伊人久久久久| 久久精品国产亚洲av麻豆蜜芽 | 色青青草原桃花久久综合| 91精品国产高清久久久久久io| 综合久久一区二区三区| 青青国产成人久久91网| 久久久久无码精品国产| 2021国产精品久久精品| 久久九色综合九色99伊人| 久久综合狠狠色综合伊人| 久久久久久无码Av成人影院| 欧美日韩精品久久免费| 久久综合视频网站| 久久免费观看视频| 999久久久免费国产精品播放| 久久99精品久久久久久动态图| 97香蕉久久夜色精品国产 | 久久久久久极精品久久久| 精品国产乱码久久久久久1区2区 | 色播久久人人爽人人爽人人片aV| 久久精品成人免费网站| 久久国产成人精品麻豆| 国产99久久精品一区二区| 久久精品国产清高在天天线| 午夜天堂av天堂久久久| 久久香综合精品久久伊人| 亚洲国产精品无码久久SM|