Lisa

这个题其实很水
$$
dp{ij}=max(dp{i-1,j-1}+a{i,j},dp{i-1,j})
$$
这是什么意思呢，到第i行放j盆花，可能上一个花瓶放的是j-1种花，也可能上一个花瓶（或更久）已经有j-1种花了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int a[101][101];
int dp[105][105];
string ans[105][105];
void print(){
    string tem=ans[m][n];
    for(int i=0;i<m;++i){
        if(tem[i]!='0'){
            printf("%lld ",i+1);
        }
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%lld",&a[i][j]);
        }
    } 
    memset(dp,-127,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=m;++i){
        dp[i][0]=0;
        ans[i][0]=ans[i-1][0]+'0';
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=i&&j<=n;++j){
            if(dp[i-1][j-1]+a[j][i]>dp[i-1][j]){
                dp[i][j]=dp[i-1][j-1]+a[j][i];
                ans[i][j]=ans[i-1][j-1]+char(j+'0');
            }else{
                dp[i][j]=dp[i-1][j];
                ans[i][j]=ans[i-1][j]+'0';
            }
        }
    }
    cout<<dp[m][n]<<endl;
    print();
    return 0;
}