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

            POJ 1157 LITTLE SHOP OF FLOWERS 動態規劃

            Description

            You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

            Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.
             

            V A S E S

            1

            2

            3

            4

            5

            Bunches

            1 (azaleas)

            7 23 -5 -24 16

            2 (begonias)

            5 21 -4 10 23

            3 (carnations)

            -21

            5 -4 -20 20

            According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

            To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

            Input

            • The first line contains two numbers: F, V.
            • The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file.


            • 1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
            • F <= V <= 100 where V is the number of vases.
            • -50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.

            Output

            The first line will contain the sum of aesthetic values for your arrangement.

            Sample Input

            3 5
            7 23 -5 -24 16
            5 21 -4 10 23
            -21 5 -4 -20 20

            Sample Output

            53

            Source

                因為題目中規定若i<j,則第i束花必須出現在第j束花之前,根據這一條件,可以用花的數目來進行動態規劃。設dp[i,j]為前i束花插在前j個花瓶中的最大美學值,有狀態轉移方程:dp[i,j]=max(dp[i-1,k-1]+A[i,k]),其中i<=k<=j,A[i,k]為第i束花插在第k個花瓶中的美學值,規定dp[i,0]=0,1<=i<=F。
            #include<iostream>
            using namespace std;

            const int MAXN = 101;
            const int inf = 10000;
            int A[MAXN][MAXN],dp[MAXN][MAXN];

            int main(){
                
            int i,j,k,f,v,t;
                
            while(scanf("%d %d",&f,&v)!=EOF){
                    
            for(i=1;i<=f;i++){
                        dp[i][
            0]=0;
                        
            for(j=1;j<=v;j++){
                            scanf(
            "%d",&A[i][j]);
                            dp[i][j]
            =-1;
                        }

                    }

                    
            for(i=1;i<=f;i++)
                        
            for(j=1;j<=v;j++)
                            
            for(t=-inf,k=i;k<=j;k++){
                                t
            =max(t,dp[i-1][k-1]+A[i][k]);
                                
            if(dp[i][j]==-1 || dp[i][j]<t)
                                    dp[i][j]
            =t;
                            }

                    printf(
            "%d\n",dp[f][v]);
                }

                
            return 0;
            }

            posted on 2009-06-16 13:57 極限定律 閱讀(1456) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC

            評論

            # re: POJ 1157 LITTLE SHOP OF FLOWERS 動態規劃 2009-11-17 21:57 Gamor

            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + A[i][j])  回復  更多評論   

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            日韩影院久久| 国产精久久一区二区三区| 一级做a爰片久久毛片16| 久久香蕉综合色一综合色88| 久久99精品国产麻豆蜜芽| 亚洲乱码精品久久久久..| 99久久精品国产一区二区蜜芽| 久久久久人妻精品一区三寸蜜桃| 69SEX久久精品国产麻豆| 亚洲国产视频久久| 国产成人精品久久亚洲高清不卡 | 国产成人久久精品激情 | 精品综合久久久久久88小说| 久久福利片| 三上悠亚久久精品| 久久国产视屏| 丁香五月网久久综合| 97精品依人久久久大香线蕉97| 久久久亚洲精品蜜桃臀 | 国产精品亚洲综合久久| 国产精品久久久天天影视香蕉| 色婷婷久久综合中文久久蜜桃av| 久久午夜综合久久| 狠狠久久综合| 色综合久久综精品| 亚洲成色999久久网站| 精品久久香蕉国产线看观看亚洲| 久久亚洲精品成人AV| 国内精品人妻无码久久久影院导航| 国产精品激情综合久久| 国产精品欧美亚洲韩国日本久久 | 少妇久久久久久被弄到高潮| 精品久久久久香蕉网| 色综合久久综合中文综合网| 久久午夜无码鲁丝片秋霞| 久久亚洲AV成人无码软件| 中文精品久久久久人妻不卡| 狠狠色综合网站久久久久久久高清| 无夜精品久久久久久| 色偷偷88888欧美精品久久久| 亚洲va中文字幕无码久久不卡|