C++ 代码

#include <iostream>
using namespace std;

int main()
{
    int f,v,a[110][110],dp[110][110],i,j,k,l,x=-100,ans[110];
    cin>>f>>v;
    for(i=1;i<=f;i++)
        for(j=1;j<=v;j++)
            {cin>>a[i][j];dp[i][j]=-10000;}
    for(i=1;i<=v;i++) dp[1][i]=a[1][i];
    for(i=2;i<=f;i++)
        for(j=1;j<=v;j++)
        {
            for(k=i-1;k<j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][k]);
            dp[i][j]+=a[i][j];
        }
    for(i=1;i<=v;i++) x=max(x,dp[f][i]);
    /*for(i=1;i<=f;i++)
    {
        for(j=1;j<=v;j++)
            cout<<dp[i][j]<<' ';
        cout<<endl;
    }*/
    cout<<x<<endl;
    i=f;k=v;
    for(j=k;j>0;j--) if(dp[f][j]==x) {k=j;ans[f-i]=k;break;}
    while(i)
    {
        i--;
        l=-10000;
        for(j=k-1;j>0;j--)
            if(dp[i][j]>l) {l=dp[i][j];k=j;}
        ans[f-i]=k;
    }
    for(i=f-1;i>=0;i--) cout<<ans[i]<<' ';
    return 0;
}