• <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 幻浪天空領(lǐng)主 閱讀(1019) 評(píng)論(1)  編輯 收藏 引用 所屬分類: SGU

            評(píng)論

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

            dp[i][i-1]=-32767;
            這句話為什么可以解決負(fù)數(shù)的問題??  回復(fù)  更多評(píng)論   


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


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

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            国产香蕉97碰碰久久人人| 99久久久国产精品免费无卡顿| 国产精品久久久久久一区二区三区| 少妇久久久久久久久久| 熟妇人妻久久中文字幕| 99久久无色码中文字幕| 四虎国产精品免费久久久| 久久频这里精品99香蕉久| 热re99久久精品国99热| 99久久精品九九亚洲精品| 久久91精品国产91久| 99久久99这里只有免费的精品| 久久99精品国产99久久6| 亚洲AV日韩AV天堂久久| 成人亚洲欧美久久久久| 久久精品麻豆日日躁夜夜躁| 老司机午夜网站国内精品久久久久久久久| 久久精品国产99久久久古代| 91精品日韩人妻无码久久不卡| 婷婷久久综合九色综合九七| 久久er国产精品免费观看2| 日韩欧美亚洲综合久久| 狠狠色伊人久久精品综合网 | 7777久久久国产精品消防器材| 久久久中文字幕| 无码国内精品久久人妻蜜桃 | 亚洲国产天堂久久久久久| 国产精品久久久天天影视| 午夜人妻久久久久久久久| 一本色道久久88综合日韩精品 | 亚洲欧美久久久久9999| 久久99精品国产麻豆不卡| 成人精品一区二区久久久| 色综合久久最新中文字幕| 99麻豆久久久国产精品免费| 久久久无码一区二区三区| 一级A毛片免费观看久久精品| 久久精品国产只有精品66 | 国产成人精品久久亚洲| 国产精品久久久久无码av| 国内精品久久国产大陆|