花店橱柜

//花店橱柜
//dp
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll mp[110][110]; //存输入数据
ll f[110][110]; //f[i][j]表示必选第1 ~ i种花放在前j个花瓶的方法
ll res[110]; // 每种花所在的花瓶
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    memset(f,-0x3f,sizeof(f));//状态初始化，一开始什么都没选

    int n,m;
    cin>> n>> m;
    for(int i=1;i<=n; i++)
        for(int j=1;j<=m;j++)   cin>>mp[i][j];


    for(int i=1;i<=m;i++)   f[1][i]=mp[1][i];//第一种花必选的话，美观值最大值就是自己

    for(int i=2;i<=n;i++)
        for(int j=i;j<=m;j++)
            for(int k=0;k<j;k++)
                f[i][j]=max(f[i-1][k]+mp[i][j],f[i][j]); // i必选的花，最大值是前i-1种花放在前j-1花瓶的最大美观值加上当前花的美观值

    res[0]=m+1;//因为第一次从第n行开始查，需要初始化一下
    int k=1;
    for(int i=n;i>= 1;i--)
    {
        ll temp=-0x3f3f3f3f3f3f3f3f;
      for(int j=res[k-1]-1;j>=1;j--)//每次行的检查，从上一次最大值所在列的左边开始，倒序检查每行最大值，保证字典序
      {
          if(f[i][j]>=temp)
          {
              temp=f[i][j];
              res[k]=j;
          }
      }
      k++;
        if(i==n)    cout<<temp<<endl;//最大美观值在最后一行
    }

    for(int i=n;i>=1;i--)
        cout<<res[i]<<" ";//倒序输出
}