• <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)論排行榜

            久久亚洲精品无码观看不卡| 久久亚洲国产成人精品性色| 一级做a爰片久久毛片16| 欧美日韩中文字幕久久伊人| 久久涩综合| 欧美精品久久久久久久自慰| 99热精品久久只有精品| 一级a性色生活片久久无| 97精品国产91久久久久久| 亚洲人成网站999久久久综合 | 国产Av激情久久无码天堂| 国内精品久久久久久久coent | 久久影院午夜理论片无码| 久久精品国产男包| 久久伊人亚洲AV无码网站| 99久久精品费精品国产一区二区| 久久综合五月丁香久久激情| 国产精品久久久久…| 狠狠综合久久综合88亚洲| 久久激情五月丁香伊人| 日本福利片国产午夜久久| 久久超碰97人人做人人爱| 亚洲人成精品久久久久| 久久中文精品无码中文字幕| 国产精品欧美久久久久天天影视| 久久久久久久波多野结衣高潮| 久久亚洲色一区二区三区| 精品久久久久久99人妻| 亚洲精品高清国产一久久| 热久久国产精品| 一级做a爱片久久毛片| 国产成人无码精品久久久久免费| 久久久久人妻一区二区三区vr| 狠狠色狠狠色综合久久| 久久精品中文字幕一区| 日韩欧美亚洲综合久久| 97精品依人久久久大香线蕉97| 精品久久久久久久久免费影院| 欧美一级久久久久久久大| 伊人久久大香线蕉精品不卡 | 久久精品国产男包|