poj 1157 dp

/* 题意：n朵花插到m个瓶子中,花必须全插，第i朵花插到第j个瓶子的价值为value[i][j],求价值的最大值
    dp[i][j]表示当第i朵花插到第j个瓶子是的价值最大值，k表示i-1可以放的位置，
    动态转移方程:dp[i][j]=MAX(dp[i][j],dp[i-1][k]+value[i][j]);
*/
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define MAX(a,b) (a)>(b)?(a):(b)
int dp[105][105];
int main()
{
    int value[105][105],i,j,k,n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
                scanf("%d",&value[i][j]);
        for(i=1; i<=n; i++)
        {
            for(j=i; j<=m; j++)
            {
                dp[i][j]=-10000;  //部分初始化，j<i时没有初始化
                for(k=i-1; k<j; k++)
                    dp[i][j]=MAX(dp[i][j],dp[i-1][k]+value[i][j]);
            }
        }
        int ans=dp[n][n];
        for(i=n; i<=m; i++)  //花必须全部放,所以从第n个开始,避免i<n时，ans]值在负数的情况下,dp[i][j]没有初始化时出现错误
            ans=MAX(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

poj 1157 dp,布布扣,bubuko.com

poj 1157 dp

原文：http://blog.csdn.net/littlefool5201314/article/details/23021217