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

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产午夜福利精品久久2021| 欧美一区二区精品久久| 久久久WWW成人免费精品| 久久97久久97精品免视看| 久久国产影院| 国产色综合久久无码有码| .精品久久久麻豆国产精品| 精品国产一区二区三区久久蜜臀| 亚洲精品美女久久久久99小说 | 国产激情久久久久影院| 亚洲国产精品久久久久网站| 中文字幕精品久久久久人妻| 国产亚洲精品自在久久| 亚洲欧美日韩精品久久亚洲区| 国产精品免费看久久久| 日批日出水久久亚洲精品tv| 国产精品久久久香蕉| 99久久婷婷国产综合亚洲| 久久久久久久免费视频| 久久国产精品久久| 亚洲日韩中文无码久久| 一本久久a久久精品综合香蕉| 欧美综合天天夜夜久久| 久久婷婷国产综合精品 | 狠色狠色狠狠色综合久久| 精品久久久久成人码免费动漫| 91麻精品国产91久久久久| 久久久久久无码Av成人影院| 久久只有这里有精品4| 久久久久婷婷| 精品久久久久久99人妻| 国产69精品久久久久9999| 久久精品九九亚洲精品天堂| 久久亚洲中文字幕精品有坂深雪| 久久久久亚洲国产| 色综合久久天天综线观看| 久久久久黑人强伦姧人妻| 狠狠色综合久久久久尤物| 国产一区二区精品久久凹凸| 久久精品国产一区| 嫩草影院久久99|