• <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結尾的排法的最大值,
            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)  編輯 收藏 引用 所屬分類: 動態規劃
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            少妇精品久久久一区二区三区| 久久久久久免费视频| 久久综合狠狠综合久久综合88| 色欲综合久久躁天天躁蜜桃| 精品久久久久久中文字幕大豆网| 热久久这里只有精品| 久久成人国产精品免费软件| 久久久久人妻精品一区二区三区| 久久国产午夜精品一区二区三区| 狠狠色狠狠色综合久久| 日本久久久久久中文字幕| 国内精品欧美久久精品| 久久午夜电影网| 国内精品伊人久久久影院| 国产成人精品综合久久久| 97精品久久天干天天天按摩| 亚洲国产美女精品久久久久∴ | 久久这里只有精品视频99| 久久精品国产亚洲av麻豆色欲| 久久亚洲高清观看| 天堂久久天堂AV色综合| 人妻中文久久久久| 久久亚洲精品无码观看不卡| 久久99国内精品自在现线| 久久精品中文字幕无码绿巨人| 久久久久国产日韩精品网站| 看久久久久久a级毛片| 热99RE久久精品这里都是精品免费 | 久久精品国产久精国产思思| 久久久久久综合网天天| 久久人人爽人人爽人人片AV麻豆 | 国产综合久久久久| 伊人久久精品无码二区麻豆| 久久久久亚洲av毛片大| 国产精品免费久久久久电影网| 久久ZYZ资源站无码中文动漫| 久久婷婷五月综合国产尤物app | 欧美亚洲另类久久综合| 99久久精品费精品国产一区二区| 97久久国产综合精品女不卡 | 久久国产精品免费一区|