C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 1157 LITTLE SHOP OF FLOWERS(简单DP)

Posted on 2012-04-10 11:23 C小加 阅读(1506) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

题意():将某些花放入某些花瓶中得到的观赏价值是不同的,并且要求开始输入的数据必须在后输入的数据前面。即:若一号花放入了3号花瓶,那么后面的花就不能放入12号花瓶了。

分析:简单DPDp[i][j]表示前i朵花按顺序放入前j 个花瓶中的最优观赏价值。

状态转移方程:dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+map[i][j])

i朵花按顺序放入前j 个花瓶中的最优观赏价值=max(前i朵花按顺序放入前j -1个花瓶中的最优观赏价值,前i-1朵花按顺序放入前j -1个花瓶中的最优观赏价值+i朵花放入j瓶中的价值)

 

注意价值可能为负数。

#include<iostream>
#include<cstdio>
using namespace std;
const int INF=0x7fffffff-1;
int map[103][103];
int dp[103][103];
int main()
{
    int f,v;
    scanf("%d %d",&f,&v);

        for(int i=1;i<=f;++i)
        {
            for(int j=1;j<=v;++j)
            {
                scanf("%d",&map[i][j]);
            }
        }
        for(int i=0;i<=f;++i)
        {
            for(int j=0;j<=v;++j)
            {
                dp[i][j]=-INF;
            }
        }
        for(int j=1;j<=v;++j)
        {
            int zc=min(j,f);
            for(int i=1;i<=zc;++i)
            {
                int temp=dp[i-1][j-1]==-INF?0:dp[i-1][j-1];
                dp[i][j]=max(dp[i][j-1],temp+map[i][j]);
            }
        }
        printf("%d\n",dp[f][v]);

    return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理