首页 > 代码库 > Poj-1157-LITTLE SHOP OF FLOWERS
Poj-1157-LITTLE SHOP OF FLOWERS
题意为从每行取一瓶花,每瓶花都有自己的审美价值
第 i+1 行取的花位于第 i 行的右下方
求最大审美价值
dp[i][j]:取到第 i 行,第 j 列时所获得的最大审美价值
动态转移方程:dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i][j-1])
代码如下:
#include<stdio.h> int dp[105][105]; int a[105][105]; int Max(int x,int y) { return x>y?x:y; } int main() { int f,v; while(scanf("%d%d",&f,&v)!=EOF) { for(int i=1; i<=f; i++) for(int j=1; j<=v; j++) { scanf("%d",&a[i][j]); dp[i][j]=-999999; } dp[1][1]=a[1][1]; for(int i=2; i<=v; i++) //初始化dp[1][2~v] dp[1][i]=Max(dp[1][i-1],a[1][i]); for(int i=2; i<=f; i++) for(int j=i; j<=v; j++) //注意从i开始,,上一行的右下方 { dp[i][j]=Max(dp[i-1][j-1]+a[i][j],dp[i][j-1]); } printf("%d\n",dp[f][v]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。