• <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>
            posts - 195,  comments - 30,  trackbacks - 0

            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.

            ASSUMPTIONS

            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.

            Input

            The first line contains two numbers: F and 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.

            Notice: The input contains several test cases.

            Output

            The output 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

            這題可以用搜索過,但是還可以用dp
            用result[i][j]表示前i行,以j結(jié)尾的排法的最大值,
            rsult[1][j]直接初始化為num[i][j];其余初始化為負無窮
            dp的過程就是
                for(i=2;i<-r;i++)//行逐漸增加
                      for(j=i;j<=c;j++)//列必須大于等于行號,否則無法保證從左上方到右下方
                                for(k=1;k<j;k++)
                                           if(result[i][j]<result[i-1][k]+num[i][j])//無需擔心不是從左上方到右下方,因為若i<j,result[][]賦為了負無窮
                                                           result[i][j]=result[i-1][k]+num[i][j]
            更詳細的代碼可以到蘇強的博客http://download.csdn.net/user/china8848/獲得
            posted on 2009-07-14 10:05 luis 閱讀(251) 評論(0)  編輯 收藏 引用 所屬分類: 動態(tài)規(guī)劃
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产福利电影一区二区三区久久老子无码午夜伦不| 国产福利电影一区二区三区久久久久成人精品综合 | 久久综合88熟人妻| 久久精品国产亚洲av麻豆小说| 精品熟女少妇a∨免费久久| a级毛片无码兔费真人久久| 思思久久99热只有频精品66| 91久久婷婷国产综合精品青草| 精品国产婷婷久久久| 欧美精品国产综合久久| 久久精品国产影库免费看| 性做久久久久久久久久久| 99久久精品免费看国产一区二区三区| 7777久久亚洲中文字幕| 亚洲欧美久久久久9999| 青草影院天堂男人久久| 久久久久亚洲精品天堂| 麻豆久久| 国产99久久久久久免费看| 99久久99这里只有免费费精品 | 99久久精品国产高清一区二区| 久久久久久亚洲精品无码| 国产精品久久99| 无码AV中文字幕久久专区| 亚洲国产成人精品女人久久久| 久久91精品国产91久久麻豆| 精品综合久久久久久98| 思思久久99热免费精品6| 国产2021久久精品| 办公室久久精品| segui久久国产精品| 88久久精品无码一区二区毛片| 国产精品无码久久综合| 人妻丰满AV无码久久不卡| 亚洲va久久久噜噜噜久久天堂| 思思久久99热只有频精品66| 中文字幕无码久久久| 热RE99久久精品国产66热| 久久精品中文字幕第23页| 久久久中文字幕日本| 色播久久人人爽人人爽人人片aV|