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

            SGU 104. Little shop of flowers

            104. Little shop of flowers

            time limit per test: 0.50 sec.
            memory limit per test: 4096 KB

            PROBLEM

            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.

            ASSUMPTIONS

            • 1 ≤ F ≤ 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.

               

            • FV ≤ 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.

               

             

            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 j’th number on the (i+1)’st line of the input file.

               

             

            Output

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

               

            • The second line must present the arrangement as a list of F numbers, so that the k’th number on this line identifies the vase in which the bunch k is put.

               

             

            Sample Input

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

            Sample Output

            53
                        2 4 5
                        
            Analysis

            It is called a problem derived from IOI. As a typical DP problem, the only thing we need to think about is the dynamic function. This problem is harder since we need to record the tracy of dynamic programing.
            Let's assume that dp[i][j] means the maximum sum of  aesthetic values about first i flowers puts in first j vases. Then, since the only choice for the ith flower is whether put or not, the function is obvious: dp[i][j]=max{dp[i][j-1],dp[i-1][j-1]+a[i][j]}. Limitness is that i<j should be held and record the action "put".

            Code
            #include <stdio.h>
            #include 
            <stdlib.h>
            #include 
            <string.h>
            #define max(a,b) a>b?a:b

            int dp[101][101];
            bool put[101][101];
            int f,v;
            int a[101][101];    

            void putprint(int i,int j){
                
            while (put[i][j]) j--;
                
            if (i>1) putprint(i-1,j-1);
                
            if (i==f) printf("%d\n",j);
                
            else printf("%d ",j);
            }


            int main(){
                
            int i,j;
                
                scanf(
            "%d %d",&f,&v);
                
            for (i=1;i<=f;i++)
                    
            for (j=1;j<=v;j++)
                        scanf(
            "%d",&a[i][j]);
                
                memset(dp,
            0,sizeof dp);
                
            for (i=1;i<=f;i++)
                    
            for (j=1;j<=v-f+i;j++){
                        dp[i][i
            -1]=-32767;
                        dp[i][j]
            =dp[i-1][j-1]+a[i][j];;put[i][j]=false;
                        
            if (dp[i][j-1]>(dp[i-1][j-1]+a[i][j])){
                            dp[i][j]
            =dp[i][j-1];
                            put[i][j]
            =true;
                        }
                            
                    }

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

            posted on 2008-11-03 14:35 幻浪天空領主 閱讀(1019) 評論(1)  編輯 收藏 引用 所屬分類: SGU

            評論

            # re: SGU 104. Little shop of flowers 2011-06-07 11:14 zqynux

            dp[i][i-1]=-32767;
            這句話為什么可以解決負數的問題??  回復  更多評論   

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产亚洲精午夜久久久久久 | 久久久国产99久久国产一| 久久成人18免费网站| 亚洲精品无码久久毛片| 亚洲精品国精品久久99热一| 99精品久久久久中文字幕| 亚洲国产天堂久久久久久| 久久久久久夜精品精品免费啦| 国产精品美女久久久| 亚洲一区精品伊人久久伊人 | 久久久久久国产a免费观看不卡| 亚洲精品tv久久久久| 久久精品国产只有精品2020| 日本精品久久久久久久久免费| 无码国内精品久久人妻| 久久精品国产清自在天天线| 日韩精品久久久肉伦网站| 久久久久久A亚洲欧洲AV冫| 久久99久久99精品免视看动漫| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 中文字幕无码久久人妻| 99久久99久久精品国产片果冻 | 久久A级毛片免费观看| 色综合久久夜色精品国产| 国内精品久久久久国产盗摄| 国产精品一区二区久久不卡| 久久久久久久久久久精品尤物| 亚洲国产精品人久久| 人妻精品久久久久中文字幕69| 久久笫一福利免费导航 | 欧美色综合久久久久久| 精品国产乱码久久久久久浪潮| 久久91精品国产91久久户| 人妻无码αv中文字幕久久 | 中文字幕精品无码久久久久久3D日动漫 | 免费久久人人爽人人爽av| 亚洲午夜精品久久久久久浪潮| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久99国产一区二区三区| 国产精品成人久久久久三级午夜电影| 精品无码久久久久久尤物|