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

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            欧美一级久久久久久久大| 99国内精品久久久久久久| 久久狠狠爱亚洲综合影院 | 久久大香萑太香蕉av| 亚洲精品无码专区久久久| 精品国产综合区久久久久久| 99久久香蕉国产线看观香| AV狠狠色丁香婷婷综合久久| 久久婷婷色香五月综合激情| 91视频国产91久久久| 久久天天躁夜夜躁狠狠| 久久精品国产只有精品66| 无码AV中文字幕久久专区| 污污内射久久一区二区欧美日韩 | 伊人久久大香线蕉影院95| 一本大道久久香蕉成人网| 91精品国产综合久久香蕉 | 国产成人久久精品一区二区三区 | 亚洲伊人久久成综合人影院 | 久久中文骚妇内射| 7777精品伊人久久久大香线蕉| 久久精品视频免费| 2021少妇久久久久久久久久| 国产精品久久久香蕉| 亚洲精品国产综合久久一线| 久久99久久成人免费播放| 久久国产福利免费| 精品久久久久久无码人妻热| 久久99毛片免费观看不卡| 东京热TOKYO综合久久精品| 色综合久久久久久久久五月| 亚洲精品乱码久久久久久蜜桃图片| 人妻无码久久精品| 久久久久久国产精品美女| 亚洲中文久久精品无码| 三上悠亚久久精品| 精品久久久久久无码中文字幕一区 | 亚洲AV无码久久寂寞少妇| 欧美va久久久噜噜噜久久| 久久综合给合久久国产免费| 国产91久久精品一区二区|