poj 动态规划DP - 1157 LITTLE SHOP OF FLOWERS

本文主要是介绍poj 动态规划DP - 1157 LITTLE SHOP OF FLOWERS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里有一份DP题目列表点击打开链接，大家想专门刷DP的可以看一下。

我们有不同的花和花瓶，每束花在不同的花瓶里有不同的价值，最后找出价值最大的放花顺序。

动态规划最重要的是找出递推式，我们将每束花在不同花瓶的价值放在data[i][j]里，map[i][j]表示第i束花插在第1-j号花瓶中全局最大的价值，递推式为：

map[i][j] = max(map[i-1][j-1]+data[i][j], map[i][j-1])

# include<stdio.h>
# define max(x,y) ( x>y ? x : y)
# define MAX 105
int map[MAX][MAX];
int data[MAX][MAX];
int ind[MAX];
int f,v;
void dp(){int i,j;map[1][1] = data[1][1];for(i = 2; i <= v; ++i) {map[1][i] = max(map[1][i-1], data[1][i]); }for(i=2;i<=f;i++){for(j=i;j<=v;j++){map[i][j] = max(map[i-1][j-1]+data[i][j], map[i][j-1]);}}printf("%d\n",map[f][v]);
}
int main(){int i,j;scanf("%d %d",&f,&v);for(i=1;i<=f;i++){ind[i]=1;for(j=1;j<=v;j++){scanf("%d",&data[i][j]);map[i][j]=0;}}dp();
}

这篇关于poj 动态规划DP - 1157 LITTLE SHOP OF FLOWERS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---