问题描述：
现在有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(F≤V)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果i<j，那么花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。
每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。
如图所示，有3束花（F）和5个花瓶（V），每束花插在不同位置的花瓶中有不同的美学价值。将花azaleas插在花瓶2中，花begonias插在花瓶4中，花carnations插在花瓶5中，即可得到最大美学值23 10 20=53。
Input
代码语言：javascript复制第一行两个正整数: F，V，F 表示花的数量，V 表示花瓶的数量。
接下来是 F 行 V 列的矩阵 A，Aij 是整数，表示 i 束花插在 j 花瓶中的美学价值。
1 <= F <= 100
F <= V <= 100
-50 <= Aij <= 50Output
代码语言：javascript复制最大美学价值，如上例中的53。解题思路：
北大OJ的1157题目；1999年的IOI题目。可以使用动态规划（DP）求解。
现约定：in[row][col] 表示第row朵花放在第col个瓶子里产生的美学值，dp[row][col] 表示总共row朵花放入col个瓶子中产生的最大美学值。
对于第row朵花，以及第col个瓶子，我们有两种选择：
- 将第row朵花放入第col个瓶子。那么此时的美学值为：
dp[row-1][col-1] in[row][col] - 不将第row朵花放入第col个瓶子，而继续向后查询。那么此时的美学值为：
dp[row][col-1]
做哪种选择，取决于哪个动作带来的美学值更高，也就是说：
dp[row][col] = max { dp[row-1][col-1] in[row][col], dp[row][col-1] }
注意：
- 初始化时只需要初始化第一行：
dp[1][1] = in[1][1], dp[1][col] = max { dp[1][col-1], in[1][col] } - 计算第 2~F 行时，只需要计算上三角形区域（因为根据 dp[row][col] 的定义，row >= col）
C 实现：
代码语言：javascript复制#include<iostream>
using namespace std;
const int maxn = 101;
int in[maxn][maxn];
int dp[maxn][maxn];
int main() {
int F, V;
cin >> F >> V;
for (int i = 1; i <= F; i ) { // 输入美学值，可能为负
for (int j = 1; j <= V; j ) {
cin >> in[i][j];
}
}
// 第1行初始化
dp[1][1] = in[1][1];
for (int i = 2; i <= V; i ) {
dp[1][i] = max(dp[1][i-1], in[1][i]);
}
// dp求解第2~F行,下三角区域不用考虑，因为无意义
for (int i = 2; i <= F; i ) {
for (int j = i; j <= V; j ) {
dp[i][j] = max(dp[i-1][j-1] in[i][j], dp[i][j-1]); // 关键转移条件
}
}
cout << dp[F][V];
return 0;
}
