Posted on 2012-04-10 11:23
C小加 阅读(1487)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
题意(转)：将某些花放入某些花瓶中得到的观赏价值是不同的，并且要求开始输入的数据必须在后输入的数据前面。即:若一号花放入了3号花瓶，那么后面的花就不能放入1，2号花瓶了。
分析：简单DP。Dp[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;
}