居然直接秒杀了
设f[i][j]表示放了i盆花,且第i盆放在j的最大价值,p[i][j]表示取到这个最大值时前一盆花放的位置
则$f[i][j]=max\ f[i-1][k]+a[i][j] (0\le k<j)$,顺便更新一下p就好了.
最后的路径递归输出.
时间复杂度$O(nm^2)$
/**********/
#define MAXN 111
ll f[MAXN][MAXN],p[MAXN][MAXN];
ll a[MAXN][MAXN];
void printway(ll i,ll j)
{
if(i==0)return;
printway(i-1,p[i][j]);
printf("%lld ",j);
}
int main()
{
memset(f,0xcf,sizeof f);
ll n=read(),m=read();
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)a[i][j]=read();
f[0][0]=0;
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
{
ll maxval=0;
for(ll k=0;k<j;++k)
if(f[i-1][k]>f[i-1][maxval])maxval=k;
f[i][j]=f[i-1][maxval]+a[i][j];
p[i][j]=maxval;
}
ll ans=0;
for(ll i=n;i<=m;++i)
if(f[n][i]>f[n][ans])ans=i;
printf("%lld\n",f[n][ans]);
printway(n,ans);
return 0;
}