一道决策状态单调递增的DP,由于每一朵花都要放,那么只用继承上一朵花的状态就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=105;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][N],pj[N][N],d[N][N];//f[i][j]表示第j个盘子放第i种颜色的花。 
void pri(int i,int j)
{
    if(!i)return ;
    pri(i-1,pj[i][j]);
    printf("%d ",j);
}
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)    
        for(int j=1;j<=m;j++)
            qr(d[i][j]);
    memset(f,0xcf,sizeof(f));
    for(int i=0;i<=m;i++)f[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        int pos=0;
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][pos]+d[i][j];
            pj[i][j]=pos;
            if(f[i-1][pos]<f[i-1][j])pos=j;
        }
    }
    int ans=0xcfcfcfcf,ansj=0;
    for(int i=1;i<=m;i++)
            if(ans<f[n][i])
            {
                ans=f[n][i];
                ansj=i;
            }
    qw(ans);puts("");
    pri(n,ansj);
    return 0;
}