POJ 1157 - LITTLE SHOP OF FLOWERS （动态规划）

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

点击打开链接

WA了两次，因为没看清题目：花是不能不插的！

d[i][j] = max ( d[i][j - 1], d[i - 1][j - 1] + a[i][j] );

表示前i束花，放在前j个花瓶的最大审美数。

//  poj 1157 (IOI 1999 - dp)
//  [6/13/2014 wind]
#include <iostream>
#include <cstdio>
using namespace std;int const MAX_N = 101, INF = 0x3f3f3f3f;
int f, v;
int a[MAX_N][MAX_N];
int d[MAX_N][MAX_N];void solve2()
{for ( int i = 1; i <= f; i++ ){d[i][i] = d[i-1][i-1] + a[i][i];for ( int j = i + 1; j <= v - f + i; j++ ){d[i][j] = max ( d[i][j - 1], d[i - 1][j - 1] + a[i][j] );}}printf ( "%d\n", d[f][v] );
}int main()
{freopen ( "in.txt", "r", stdin );scanf ( "%d%d", &f, &v );for ( int i = 1; i <= f; i++ ){for ( int j = 1; j <= v; j++ ){scanf ( "%d", &a[i][j] );}}solve2();return 0;
}

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

---