POJ1157 LITTLE SHOP OF FLOWERS dp

z4zr 2013-05-11 PM 2210℃ 0条

http://poj.org/problem?id=1157
题目描述很麻烦。。。。
举个栗子把~~
输入
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
输出
53

3表示行,5表示列,然后在下面的3行5列每一行选一个数,使这3个数最大,要求选的数列数必须依次增大,就是从左上方向右下方选3个数使和最大。
行数<=列数

f 行数 v列数
定义一个dp[][]数组存储结果
首先将第一行存入dp数组
接下来从第i行的 <span style="text-decoration: underline">第i个数</span><=(字用j表示)开始到第v-(f-i)个数
寻找i-1行的 第i-1个数到第j个数的dp[i-1][]中最大的)数字加上numi赋值给dpi

完成后 在dp的最后一行 选择最大的数字(开始一直忽略了这个东西 认为dpf是最大的 结果wa了好多次。。。)

#include
#include
int dp[102][102];
int num[102][102];
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int f,v,i,j,k,buf;
    while(scanf("%d%d",&f,&v)!=EOF){
        for(i=1;i<=f;i++){
            for(j=1;j<=v;j++){
                scanf("%d",&num[i][j]);
            }
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=v;i++){dp[1][i]=num[1][i];}
        for(i=2;i<=f;i++){
            for(j=i;j<=v;j++){
                for(k=i-1;k<j;k++){
                    if(dp[i][j]<dp[i-1][k]+num[i][j]){
                        dp[i][j]=dp[i-1][k]+num[i][j];
                    }
                }
            }
        }
        int maxn=dp[f][f];
        for(i=f+1;i<=v;i++){
            if(maxn<dp[f][i])maxn=dp[f][i];
        }
/*
        for(i=0;i<=f;i++){
            for(j=0;j<=v;j++){
                printf("%5d",dp[i][j]);
            }
            puts(");
        }
*/
        printf("%d\n",maxn);

    }
    return 0;
}

心中总是暗暗的不爽。。。可能是读题不明确把。。。
用@代表每行取得的最大值 用*表示其他的数字
@*
@*
@*
额 像这样的倒序程序就垮了。。
还有
@*
@*
@*
额 不过题目似乎表明了 是一直向右的。。

标签: C/C++, dp, poj, acm

非特殊说明,本博所有文章均为博主原创。

评论啦~