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

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久亚洲国产| 国产精品美女久久久久久2018| 一本大道加勒比久久综合| 国产精品久久久久久久久久免费| 品成人欧美大片久久国产欧美... 品成人欧美大片久久国产欧美 | 久久久久久狠狠丁香| 久久AAAA片一区二区| 亚洲综合伊人久久综合| 国产精品免费久久| 人妻无码中文久久久久专区| 理论片午午伦夜理片久久| 国内精品伊人久久久久av一坑 | 久久久亚洲欧洲日产国码是AV| 久久亚洲AV成人出白浆无码国产| 99久久精品九九亚洲精品| 久久久精品2019免费观看| 久久午夜免费视频| 久久99热这里只有精品国产| 69久久精品无码一区二区| 久久综合给合久久狠狠狠97色69 | 国产精品久久久久久久久免费| 日本五月天婷久久网站| 久久露脸国产精品| 亚洲va国产va天堂va久久| 国内精品免费久久影院| 久久人人爽人人爽人人AV东京热| 亚洲精品成人久久久| 久久精品亚洲男人的天堂| 久久香蕉国产线看观看99| 潮喷大喷水系列无码久久精品| 久久强奷乱码老熟女网站 | 久久人人爽人人爽人人片av麻烦| 中文字幕无码久久精品青草| 久久免费小视频| 91精品国产综合久久香蕉| 日本三级久久网| 大香网伊人久久综合网2020| 久久国产三级无码一区二区| 久久影视综合亚洲| 久久成人国产精品免费软件| 久久久久亚洲精品天堂|