青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

POJ 1157 LITTLE SHOP OF FLOWERS 動態規劃

Description

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.

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 jth number on the (i+1)st line of the input file.


  • 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.

Output

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

Source

    因為題目中規定若i<j,則第i束花必須出現在第j束花之前,根據這一條件,可以用花的數目來進行動態規劃。設dp[i,j]為前i束花插在前j個花瓶中的最大美學值,有狀態轉移方程:dp[i,j]=max(dp[i-1,k-1]+A[i,k]),其中i<=k<=j,A[i,k]為第i束花插在第k個花瓶中的美學值,規定dp[i,0]=0,1<=i<=F。
#include<iostream>
using namespace std;

const int MAXN = 101;
const int inf = 10000;
int A[MAXN][MAXN],dp[MAXN][MAXN];

int main(){
    
int i,j,k,f,v,t;
    
while(scanf("%d %d",&f,&v)!=EOF){
        
for(i=1;i<=f;i++){
            dp[i][
0]=0;
            
for(j=1;j<=v;j++){
                scanf(
"%d",&A[i][j]);
                dp[i][j]
=-1;
            }

        }

        
for(i=1;i<=f;i++)
            
for(j=1;j<=v;j++)
                
for(t=-inf,k=i;k<=j;k++){
                    t
=max(t,dp[i-1][k-1]+A[i][k]);
                    
if(dp[i][j]==-1 || dp[i][j]<t)
                        dp[i][j]
=t;
                }

        printf(
"%d\n",dp[f][v]);
    }

    
return 0;
}

posted on 2009-06-16 13:57 極限定律 閱讀(1471) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC

評論

# re: POJ 1157 LITTLE SHOP OF FLOWERS 動態規劃 2009-11-17 21:57 Gamor

dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + A[i][j])  回復  更多評論   

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            麻豆av一区二区三区| 国产综合网站| 欧美极品aⅴ影院| 欧美日韩精品在线| 国产精品久久久一区二区| 国产精品网站一区| 亚洲国产另类久久久精品极度| 一个色综合导航| 小黄鸭视频精品导航| 美乳少妇欧美精品| 99re8这里有精品热视频免费| 亚洲午夜精品福利| 久久久久久久久久久一区| 亚洲国产精品成人va在线观看| 亚洲激情欧美| 最新精品在线| 久久精品论坛| 国产精品mm| 亚洲精品一区二区网址| 久久福利电影| 国产精品99久久久久久有的能看| 久久久亚洲国产天美传媒修理工| 国产精品电影网站| 99精品欧美一区二区三区| 一区二区欧美日韩| 国产一区二区高清| 午夜在线精品偷拍| 一本色道久久综合狠狠躁篇的优点| 国产精品一页| 亚洲免费在线| 一区二区三区四区国产精品| 亚洲一级片在线看| 欧美精品v国产精品v日韩精品 | 欧美大片在线观看一区二区| 黑人巨大精品欧美一区二区小视频| 一区二区三区国产精华| 免费亚洲一区二区| 欧美一区二区视频观看视频| 国产精品自拍网站| 亚洲黄色一区| 狠狠久久亚洲欧美| 亚洲一区国产视频| 国产亚洲女人久久久久毛片| 亚洲精品中文字| 欧美精品一区二区三区很污很色的| 亚洲精品美女在线观看| 欧美一区视频| 亚洲欧美伊人| 久久国产精品一区二区三区| 在线观看视频免费一区二区三区| 久久日韩精品| 毛片一区二区| 久久国产主播| 欧美bbbxxxxx| 午夜精品久久久久久久99热浪潮| 久久国产精品亚洲77777| 欧美午夜精品久久久久久浪潮| 欧美大片第1页| 美女被久久久| 浪潮色综合久久天堂| 欧美成年人在线观看| 老色鬼精品视频在线观看播放| 国产精品日日摸夜夜摸av| 亚洲免费观看高清完整版在线观看熊| 国产精品国产福利国产秒拍| 亚洲黄色在线观看| 99视频精品在线| 亚洲免费中文字幕| 国内精品视频一区| 欧美在线观看视频一区二区三区| 亚洲国产经典视频| 亚洲天堂久久| 欧美在线视频导航| 国产日本欧美一区二区三区在线| 久久这里只有精品视频首页| 欧美日本在线看| 一区二区电影免费观看| 亚洲一级在线观看| 国产精品理论片| 午夜精品亚洲一区二区三区嫩草| 久久精品在线播放| 亚洲丁香婷深爱综合| 欧美成人情趣视频| 日韩视频永久免费| 亚洲欧美日本日韩| 韩国一区二区三区在线观看| 久久综合九色九九| 羞羞漫画18久久大片| 国产精品一区二区三区乱码| 欧美在线观看天堂一区二区三区| 久久久久久久综合| 亚洲精品乱码久久久久久日本蜜臀 | 99精品欧美一区二区三区| 欧美午夜久久久| 欧美亚洲免费| 欧美激情一区二区三区四区| 欧美三级网址| 亚洲欧洲视频| 欧美一级夜夜爽| 91久久精品国产91久久| 久久精品免费| 亚洲精品免费观看| 亚洲国产一区在线观看| 欧美另类极品videosbest最新版本| 亚洲一区二区三区四区中文| 免费观看成人www动漫视频| 99热精品在线观看| 国产一区二区0| 欧美日韩一区二区在线播放| 亚洲免费电影在线| 国产精品夫妻自拍| 久久综合久久88| 亚洲欧美www| 日韩视频在线一区二区三区| 久久精品盗摄| 亚洲四色影视在线观看| 欧美日韩一区二区在线观看视频| 欧美一站二站| 亚洲女同同性videoxma| 亚洲国产精品一区二区三区| 久久本道综合色狠狠五月| 亚洲图片在线| 日韩特黄影片| 在线电影院国产精品| 国产精品综合av一区二区国产馆| 裸体一区二区| 久久综合九色综合欧美就去吻| 亚洲欧美成人精品| 中日韩美女免费视频网站在线观看| 欧美国产极速在线| 美女视频黄免费的久久| 久久岛国电影| 久久精品麻豆| 久久精品久久综合| 亚洲欧美综合国产精品一区| 在线视频精品一| 999在线观看精品免费不卡网站| 亚洲第一精品在线| 美日韩在线观看| 久久久久久一区| 久久躁日日躁aaaaxxxx| 久久久久国产精品午夜一区| 久久超碰97人人做人人爱| 欧美一级一区| 久久国产精品99久久久久久老狼 | 亚洲精品四区| 亚洲免费高清| 国产日本亚洲高清| 国产精品亚洲一区二区三区在线| 国产精品a久久久久| 国产精品久久午夜夜伦鲁鲁| 国产精品黄色| 国产乱码精品| 国产一区深夜福利| 在线观看欧美| 亚洲精品乱码| 亚洲天堂免费在线观看视频| 亚洲欧美激情精品一区二区| 香蕉乱码成人久久天堂爱免费| 香蕉久久夜色精品国产| 久久国产精品久久久久久久久久| 久久综合免费视频影院| 欧美激情网友自拍| 日韩亚洲不卡在线| 午夜精品福利在线| 亚洲日本在线观看| 亚洲一区二区高清| 久久久国产精品亚洲一区| 久久在线精品| 欧美视频在线视频| 国产午夜精品在线观看| 欧美美女bbbb| 国产精品一区一区三区| 在线日韩视频| 亚洲一区二区三区精品在线观看| 先锋影音久久久| 欧美国产日韩免费| 亚洲伊人一本大道中文字幕| 久久久久久国产精品一区| 欧美乱大交xxxxx| 国产亚洲精品aa| 亚洲精品日韩一| 午夜在线精品偷拍| 亚洲黄色高清| 久久av二区| 欧美午夜视频| 亚洲人成亚洲人成在线观看图片| 亚洲欧美美女| 亚洲区一区二区三区| 欧美一区二区精品在线| 欧美日韩综合在线| 亚洲第一综合天堂另类专| 午夜精品一区二区三区在线视| 欧美激情视频一区二区三区免费 | 国产一区二区黄| 在线一区欧美| 亚洲高清中文字幕| 亚洲国产精品久久久久秋霞影院 | 欧美精品不卡| 亚洲第一精品夜夜躁人人躁|