题目描述

blablabla

样例

blablabla

算法1

(线性DP) $O(n^3)$

线性DP：f[][]分别记录当前是第i种，且放到第j个花瓶得最大得值。
转移：f[i][j]=f[i-1][k] k表示上一次选的是哪一种。
注意这题有负数，所以f[][]应该初始化为-03f3f3f3f.
还有一点，枚举k得时候应该从0开始，否则j==1得方案无法被枚举到

时间复杂度

O(n^3)

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3+10;

typedef long long ll;

int n,m;
int map1[N][N];
int f[N][N];
//pii g[N][N];

struct node
{
    int x,y,z;
}g[N][N];

void dfs(int x,int y)
{
    if(!x&&!y) return ;

    int x1=g[x][y].x,y1=g[x][y].y,z1=g[x][y].z;
    dfs(x1,y1);
    if(z1)
    cout<<z1<<" ";

}

int main()
{
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) f[i][j]=-0x3f3f3f3f;

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) 
        cin>>map1[i][j];

    for(int i=0;i<=m;i++) f[0][i]=0;

    //cout<<f[0][1];
    //这里为啥j==1时没有被遍历到
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)//枚举当前花放的地方
    for(int k=0;k<j;k++)//枚举上一种花放得地方
    {
    if(f[i][j]<f[i-1][k]+map1[i][j])
    {
        f[i][j]=f[i-1][k]+map1[i][j];

        g[i][j]={i-1,k,j};
    }
    }

    int maxv=-0x3f3f3f3f,max1=0;
    for(int i=1;i<=m;i++)
    if(maxv<f[n][i])
    {
        maxv=f[n][i];
        max1=i;
    }

   // cout<<f[1][1];
    cout<<maxv<<'\n';
    dfs(n,max1);

    return 0;
}