Posted on 2012-04-10 11:23
C小加 閱讀(1521)
評論(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;
}