原题链接

题解

第 \(i\) 朵花的选择范围为 \([i,m-n+i]\) ，而它一定是由第 \(i-1\) 朵花的某种选择继承而来的

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[105][105]={0},pre[105][105]={0},a[105][105];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }


    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=m-n+i;j++)
        {

            int maxs=-2e9,index=0;
            for(int k=i-1;k<j;k++)//注意这里是i-1不是1
            {
                if(dp[i-1][k]>maxs)
                {
                    maxs=dp[i-1][k];
                    index=k;
                }
            }


            if(i!=1)
            {
                dp[i][j]=a[i][j]+maxs;//有没有前缀
                pre[i][j]=index;//第i朵花放第j个花瓶里的最大值，第i-1朵花放的地方
            }
            else dp[i][j]=a[i][j];
        }
    }

    int index,maxs=-2e9;
    for(int i=n;i<=m;i++)
    {
        if(dp[n][i]>maxs)
        {
            maxs=dp[n][i];
            index=i;//找到最后一朵花放的地方
        }
    }

    stack<int> ans;
    ans.push(index);
    for(int i=n;i>=2;i--)
    {
        index=pre[i][index];
        ans.push(index);
    }

    cout<<maxs<<"\n";
    while(ans.size())
    {
        cout<<ans.top()<<" ";
        ans.pop();
    }
    return 0;
}