(dp)

$f[i][j]$表示在i上放j，i-1前放j-1种花的最大价值。
为了保证字典序最小，所以从n到1开始枚举。

时间复杂度

$O(nmm)$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=110;
LL f[N][N],a[N][N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=m;++j)
            cin>>a[i][j];
    memset(f,-0x3f,sizeof f);
    for(int i=n+1;i>=1;--i){
        for(int j=1;j<=m+1;++j){
            if(i==n+1) f[i][j]=0;
            else if(j!=m+1){
                for(int k=j+1;k<=m+1;++k)
                    f[i][j]=max(f[i][j],f[i+1][k]+a[i][j]);
            }
        }
    }
    LL ans=-1e18;
    for(int i=1;i<=m;++i) ans=max(ans,f[1][i]);
    cout<<ans<<'\n';
    int i=1,j=1,v=ans;
    while(i<=n){
        for(int k=j;k<=m;++k){
            if(f[i][k]==v) {
                v-=a[i][k];
                cout<<k<<' ';
                j=k+1;
                break;
            }
        }
        ++i;
    }
    return 0;
}