1157 LITTLE SHOP OF FLOWERS【DP插花】

1157 LITTLE SHOP OF FLOWERS【DP插花】

题目大意

您想以最舒适的方式布置花店的橱窗。 您有F束鲜花，每束花的种类不同，并且至少连续订购了许多花瓶。 将花瓶粘在架子上，并从左到右从1到V连续编号，其中V是花瓶的数量，因此花瓶1是最左边的，花瓶V是最右边的花瓶。 这些束是可移动的，并且由1到F之间的整数唯一地标识。这些id号具有重要意义：它们确定花瓶行中花束的出现顺序，因此，束i必须在花瓶中 每当i <j时，花瓶的左侧装有束j。 例如，假设您有一束杜鹃花（id-number = 1），一束秋海棠（id-number = 2）和一束康乃馨（id-number = 3）。 现在，必须将所有的束放入花瓶中，并保持其编号一致。 杜鹃花束必须在秋海棠左侧的花瓶中，而秋海棠束必须在康乃馨左侧的花瓶中。 如果花瓶多于束鲜花，多余的花瓶将被留空。 一个花瓶只能容纳一束鲜花。

思路分析

• 必须将所有的束放入花瓶中，并保持其编号一致。
• 有负值初始化需注意

虽然是一道简单题，但是感觉自己对最优子结构的理解得到了提升。设 d p [ i ] [ j ] dp[i][j] dp[i][j]为前i个花用前j个花瓶所能取得的最大值，因此状态转移只有两种可能

• 前i-1个花用前j-1个花瓶，第i个花用第j个花瓶 d p [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] dp[i-1][j-1]+a[i][j] dp[i−1][j−1]+a[i][j]
• 前i个花用前j-1个花瓶 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1]

二者取最大值即可，注意有负值因此初始化为-inf。当然第一行都是0.

#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;#define MAX 105
#define inf 1e10
#define ll intll a[MAX][MAX], dp[MAX][MAX];
ll F, V, res = 0;int main() {scanf("%d%d", &F, &V);for (int i = 1; i <= F; i++) {for (int j = 1; j <= V; j++) {scanf("%d", &a[i][j]); dp[i][j] = -inf;}}dp[1][0] = -inf;for (int i = 1; i <= F; i++) {for (int j = i; j <= V; j++) {dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + a[i][j]);}}printf("%d", dp[F][V]);
}