题解 | #花店橱窗#

Description

有 $n$ 朵花, $m$ 个花瓶, 每朵花插在不同的花瓶都会产生不同的价值(正负数都有)。

你要按顺序依次将 $n$ 朵花插入 $m$ 个花瓶中，并保证第 $i$ 朵花插入的位置 $pos_i$ 满足 $pos_1 < pos_2<...<pos_{n - 1} < pos_n$

求满足条件的插完 $n$ 朵花的价值和的最大值。
打印价值和最大时从小到大插花的花瓶位置

Solution

对于问题一：

考虑将第 $i$ 朵花插入第 $j$ 位时代价和的最大值。记为 $g_{i,j}$ 。

发现状态只跟 $g_{i,(i,.....,j-1)}$ 和 $g_{i-1,(i-1, .... ,j-1)}$ 有关

但是这样暴力转移的复杂度高，需要优化。

不妨将 $f_{i,j}$ 记为第 $i$ 朵花插在前 $j$ 个花瓶处代价的最大值。

此时的状态就只跟 $f_{i,j-1}$ 和 $f_{i - 1,j - 1}$ 相关联

所以我们就得到了状态转移方程 $f_{i,j} = max(f_{i,j-1},f_{i-1,j- 1} \dotplus val_{i,j})$

注意当 $i == j$ 时我们要强制转移，因为此时第 $i$ 朵花必须插在第 $i$ 个花瓶处

对于问题二:

由于我们已经得到了第 $i$ 朵花插在前 $j$ 个花瓶时的最大值，我们就能够从后往前遍历寻找第一个 $k$ 满足 $f_{i,k} \ne f_{i,j}$ 的值, $k 1$ 就是插第 $i$ 朵花的位置。如此反复即可。

code

#include <bits/stdc++.h>
#define ull unsigned long long int 
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 1e9 + 7;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

int a[120][120];
int f[120][120];
/*
f[i][j] 前i朵花插在前j个瓶子中的最大美学值。
if(i == j)) f[i][j] = f[i - 1][j - 1] + a[i][j]; 必须插
*/

void dfs(int x,int y){
    if(x == 0) return ;
    while(f[x][y] == f[x][y - 1]) y --;
    dfs(x - 1,y - 1);
    cout << y << " ";
    
}

void slove(){
    int n  = read(),m = read();
    for(int i = 1;i <=n;i ++){
        for(int j = 1;j <= m;j ++){
            a[i][j] = read();
        }
    }

    for(int i = 1;i <= n;i ++){
        for(int j = i;j <= m;j ++){
            if(i == j){
                f[i][j] = f[i - 1][j - 1] + a[i][j];
                continue;
            }
            f[i][j] = max(f[i][ j - 1],f[i - 1][j - 1] + a[i][j]);
        }
    }
    cout << f[n][m] << endl;
    dfs(n,m);
}

signed main(){
    int T = 1;
    //T = read();
    while(T --){
        slove();
    }
    return 0;
}