题目描述

算法1

(暴力枚举) $O(nm^2)$

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

typedef long long LL;

const int N=110;
int n,m;
int a[N][N];
LL f[N][N];
int p[N][N];    //记录方案：i种花在第j列的时候，i-1种花在哪里。

void get_path(int i,int j)
{
    if(i==0) return ;
    get_path(i-1,p[i][j]);
    printf("%d ",j);
}

int main()
{
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    memset(f,0xcf,sizeof f);

    f[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int pos=0;
            for(int k=0;k<j;k++)
            {
                if(f[i-1][k]>f[i-1][pos]) pos=k;
            }
            f[i][j]=f[i-1][pos]+a[i][j];
            p[i][j]=pos;
        }
    }

    LL ans=0;

    for(int i=n;i<=m;i++)
    {
        if(f[n][i]>f[n][ans]) ans=i;
    }

    cout<<f[n][ans]<<endl;

    get_path(n,ans);


    return 0;
}