• <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久久精品免费观看国产| 亚洲国产成人久久综合碰| 无码国内精品久久人妻蜜桃| 国产91色综合久久免费分享| 久久99久久成人免费播放| 亚洲女久久久噜噜噜熟女| 国产一区二区三精品久久久无广告| 久久影院亚洲一区| 久久精品www| 国产成人精品综合久久久| 久久精品成人免费观看97| 少妇久久久久久被弄高潮| 日本国产精品久久| 国产精品久久久久久搜索| 亚洲精品无码成人片久久| 久久青青草原精品国产软件| 国产亚洲美女精品久久久久狼| 超级碰碰碰碰97久久久久| 久久精品成人免费国产片小草| 国产精品久久亚洲不卡动漫| 久久九九精品99国产精品| 一日本道伊人久久综合影| 久久久WWW免费人成精品| 精品免费tv久久久久久久| 久久久久女人精品毛片| 狠狠色综合网站久久久久久久高清| 久久se精品一区二区影院 | 精品久久久久中文字幕日本| 国产香蕉久久精品综合网| 无码人妻少妇久久中文字幕 | 热久久国产精品| 国产精品久久久久9999| 97久久综合精品久久久综合| 国产精品久久影院| 国产亚洲美女精品久久久| 很黄很污的网站久久mimi色 | 一本一本久久A久久综合精品|