首页 > 代码库 > poj - 1157 - LITTLE SHOP OF FLOWERS(dp)
poj - 1157 - LITTLE SHOP OF FLOWERS(dp)
题意:F朵花(从左到右标号为1到F,1 <= F <= 100)放入V个花瓶(从左到右标号为1到V,F <= V <= 100),花 i 要放在花 j 的左边,如果i < j,每朵花放入每个花瓶有一个好看度(-50 <= Aij <= 50),求所有花放入花瓶后的最大好看度和。
——>>设dp[i][j]表示将前j种花放入前i个花瓶的最大好看度和,则状态转移方程为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + nValue[j][i]);
时间复杂度:O(F * V)
#include <cstdio> #include <algorithm> using std::max; const int MAXN = 100 + 10; int nValue[MAXN][MAXN]; int dp[MAXN][MAXN]; int F, V; void Read() { for (int i = 1; i <= F; ++i) { for (int j = 1; j <= V; ++j) { scanf("%d", &nValue[i][j]); } } } void Dp() { int nRet = 0; dp[0][0] = 0; for (int i = 1; i <= V; ++i) { dp[i][0] = 0; for (int j = 1; j <= i && j <= F; ++j) { dp[i][j] = dp[i - 1][j - 1] + nValue[j][i]; if (i - 1 >= j) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); } if (j == F) { nRet = max(nRet, dp[i][j]); } } } printf("%d\n", nRet); } int main() { while (scanf("%d%d", &F, &V) == 2) { Read(); Dp(); } return 0; }
poj - 1157 - LITTLE SHOP OF FLOWERS(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。