【POJ1157】LITTLE SHOP OF FLOWERS (简单动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: 4 Comments
Published on: 2011 年 04 月 25 日

该题也是经典的动态规划,题目叙述的依然很麻烦,其实简化一下就是这样的:例如下面这个例子就是:3表示行,5表示列,然后在下面的3行5列每一行选一个数,使这3个数最大,要求选的数列数必须依次增大,就是从左上方想右下方选3个数使和最大。
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
状态转移方程 arr[i][j]=max{arr[i-1][ 0...(j-1)]}+arr[i][j];

其中arr[][]存储的是当前最优值

#include <iostream>  
using namespace std;  
#define maxlen 102  
int arr[maxlen][maxlen];  
int main(){  
    freopen("1.txt","r",stdin);  
    int n,m,max;  
    while(cin>>n>>m){  
        for (int i=0;i<n;i++)  
            for (int j=0;j<m;j++)  
                cin>>arr[i][j];  
        for (int i=1;i<n;i++){  
            for (int j=i;j<m;j++){  
                max=-99999;  
                for (int k=0;k<j;k++)  
                    if(max<arr[i-1][k]) max=arr[i-1][k];  
                arr[i][j]+=max;  
            }  
        }  
        max=-99999;  
        for (int i=0;i<m;i++)  
            if(max<arr[n-1][i]) max=arr[n-1][i];  
        cout<<max<<endl;  
    }  
}  

我猜你可能也喜欢:

4 Comments - Leave a comment
  1. 三江小渡说道:

    特色

  2. 三江小渡说道:

    test

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日