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

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久久精品无码人妻| 久久婷婷国产麻豆91天堂| 久久精品亚洲AV久久久无码| 囯产极品美女高潮无套久久久 | 久久香蕉综合色一综合色88| 国产精品丝袜久久久久久不卡| 色偷偷91久久综合噜噜噜噜| 久久久久AV综合网成人| 久久国产精品一区| 久久久久人妻精品一区二区三区| 久久播电影网| 青青国产成人久久91网| 久久久久亚洲AV无码专区体验| 久久精品亚洲乱码伦伦中文| 久久亚洲国产成人精品性色| 麻豆久久| 久久丝袜精品中文字幕| 久久综合狠狠色综合伊人| 国内精品人妻无码久久久影院导航| 欧美日韩中文字幕久久伊人| 国产亚洲综合久久系列| 国色天香久久久久久久小说| 久久涩综合| 欧美日韩精品久久久免费观看| 97精品伊人久久久大香线蕉| 国产精品免费看久久久| 久久亚洲精精品中文字幕| 午夜久久久久久禁播电影| 久久乐国产综合亚洲精品| 国产精品一区二区久久精品无码 | 欧美亚洲另类久久综合| 久久99精品综合国产首页| 丰满少妇高潮惨叫久久久| 亚洲国产精品无码久久久秋霞2| 亚洲国产精品成人AV无码久久综合影院| AV无码久久久久不卡网站下载 | 久久久久久久97| 久久九九有精品国产23百花影院| 国产精品久久久久…| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 久久热这里只有精品在线观看|