题意

• 花店有f朵花，v个盆，每个花放每个盆有不同的美观度，求如何摆放能使美观度最大
• 特别的，给花编上号，花必须按照顺序摆放，编号小的的花不能放在编号大的花的后面

思路

• 由于必须按照顺序摆放，所以新的一盆花可放的盆一定是上一盆花放的盆的后面
• 
• 
• 初始化:对于最开始，每朵花放在自己编号的盆里，其它位置都放极小值即可
• 对于输出路径，使用记录到(i,j)这个点是谁转移来的，然后dfs回溯即可

代码

#include<bits/stdc++.h>
using namespace std;
/**
 * 所有的花束在放入花瓶时必须保持其标识数的顺序，即：
 * 杜鹃花必须放在秋海棠左边的花瓶中
 * 秋海棠必须放在康乃馨左边的花瓶中
 * dp[i][j]表示前i朵花，用前j个盆且第i朵花放到第j个盆里最大价值
 * dp[i][j]=dp[i-1][1~j-1]+a[i][j]
 * 初始化：没放的时候每个位置都应该是极小值，第0行应该是0,便于转移，每个花盆放在最小位置需要手动初始化
 */
long long dp[120][120];
long long val[120][120];
int path[120][120];

void printpath(int n,int dep){
    if(dep==0) return;
    printpath(path[dep][n],dep-1);
    cout << n << ' ' ;
}
int main(){
    int f,v;
    cin >> f >> v;

    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++){
            cin >> val[i][j];
        }
    }
    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++){
            dp[i][j]=-0x3f3f3f3f;
            if(i==j){
                dp[i][j]=dp[i-1][j-1]+val[i][j];
                path[i][j]=i-1;
            }            
        }        
    }
    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++){
            for(int k=1;k<j;k++){
                if(dp[i][j]<dp[i-1][k]+val[i][j]){
                    dp[i][j]=dp[i-1][k]+val[i][j];
                    path[i][j]=k;
                }
            }
        }
    }
    long long ans=-0x3f3f3f3f;
    int idx=-1;
    for(int i=f;i<=v;i++){
        if(dp[f][i]>ans){
            ans=dp[f][i];
            idx=i;
        }
    }
    cout << ans << endl ;
    printpath(idx,f);
    return 0;

}