【算法分析】
1. 状态定义
状态定义：dp[i][j]：将前i束花放入前j个瓶子中，美学值最大的方案的美学值。
初始状态：前0束花放入j个花瓶中，美学值为0。所以dp[0][j] = 0。
2. 状态转移方程
记将第i束花放入第j个瓶子得到的美学值为a[i][j]。
集合：将前i束花放入前j个瓶子
分割集合：根据将第i束花放入第几个瓶子来分割集合
如果把第i束花放入第j个瓶子，那么接下来需要把前i-1束花放入前j-1个瓶子中获得最大美学值。dp[i][j] = dp[i-1][j-1] + a[i][j]
如果把第i束花放入第j-1个瓶子，那么接下来需要把前i-1束花放入前j-2个瓶子中获得最大美学值。dp[i][j] = dp[i-1][j-2] + a[i][j-1]
…
如果把第i束花放入第i个瓶子，那么接下来需要把前i-1束花放入前i-1个瓶子中获得最大美学值。dp[i][j] = dp[i-1][i-1] + a[i][i]
以上多种情况取最大值。
综上，k从i循环到j，dp[i][j] = max(dp[i][j], dp[i-1][k-1] + a[i][k])
3. 具体做法：
1. 瓶子编号j的循环范围
由于每束花都要放在某个花瓶中，前i束花放入前j个瓶子中，瓶子数量必须大于等于花的数量，所以j ≥ i。
一共有f束花v个瓶子，在前i束花放入前j个瓶子时，还剩下f-i束花，v-j个瓶子，剩下的瓶子的数量也一定要大于等于花的数量，因此v ? j ≥ f ? i ，即j ≤ v ? f + i
所以j从i循环到v-f+i。
2. 记录方案
设数组b，b[i][j]表示如果将前i束花放入前j个瓶子，第i束花所在的瓶子。
如果确定将花放入第k瓶子能获得最大美学值，可以更新dp[i][j]，那么也同时更新b[i][j] = k。
输出时通过递归的方法逆序输出，前i束花放入前j个瓶子，第i束花在b[i][j]，那么先输出前i-1束花放在前b[i][j]-1个瓶子中的情况，再输出b[i][j]。
【参考代码】
?
#include<bits/stdc++.h>
using namespace std;
#define N 105
int f, v, a[N][N], dp[N][N];//dp[i][j]:前i个束花放在前j个花瓶中能得到的最大美学度
int b[N][N];//b[i][j]:前i个花束放入前j个瓶子，第i束花在哪个瓶子
void show(int i, int j)//输出前i个花束放入前j个瓶子各花束的位置
{
if(i == 0)
return;
show(i-1, b[i][j]-1);
cout << b[i][j] << ' ';
}
int main()
{
cin >> f >> v;
for(int i = 1; i <= f; ++i)
for(int j = 1; j <= v; ++j)
cin >> a[i][j];
memset(dp, 0xc0, sizeof(dp));//初始化为负无穷
for(int j = 0; j <= v; ++j)
dp[0][j] = 0;
for(int i = 1; i <= f; ++i)
for(int j = i; j <= v-f+i; ++j)
for(int k = i; k <= j; ++k)
{
if(dp[i][j] < dp[i-1][k-1] + a[i][k])
{
dp[i][j] = dp[i-1][k-1] + a[i][k];
b[i][j] = k;
}
}
cout << dp[f][v] << endl;
show(f, v);
return 0;
}