题解 P1854 【花店橱窗布置】

· · 题解

不一样的动态规划

update on 2025.6.18

更新了文章结构/排版，优化了代码实现。

我看了很多篇题解，发现大佬们都是以枚举第i束花放在哪个花瓶来进行动态规划的，事实上如果从另一个方向定义状态，则会简单很多。

题意就不多说了，进入正题：

状态定义

动态规划最重要的一步如何定义良好的状态。首先，对于本题，会有两种直观的状态定义方式：

看上去两种定义方法似乎区别不大。

如果你觉得 方案二 更简单，那么恭喜你，你的直觉是对的。无论是代码实现，抑或是时间复杂度（在不对转移方程进行优化的情况下），2 都是要优于 1 的。

如果你觉得 方案一 更简单，那么可以详细阅读方案一的部份，了解一点状态转移方程的优化技巧（方案一可能略显复杂，但请不要害怕，这种优化技巧在之后的很多题目中都会用到）。

方案一

我们按照 1 的方式定义状态，思考如何求出状态转移方程。

思考如何令 f(i, j) 从 f(i - 1, \cdots) 转移过来。

我们发现，光有 i 和 j 是不够的，因为我们无法确定第 i-1 束花放在了哪个花瓶，也就找不到转移前的状态。

因此，我们还需要枚举一个 k，表示第 i - 1 束花放在了第 k 个花瓶，然后从中找到一个最大的 f(i - 1, k) 进行转移。于是可以推出状态转移方程：

f(i, j) = \max\limits_{i-1\le k\le j - 1}\{ f(i - 1, k) \} + a_{i, j}

为什么 k 的范围是 [i-1, j-1]？（留给读者自行思考）

此时，我们枚举了 3 个变量 i, j, k，因此复杂度是 O(FV^2)。

其实这个状态转移方程还可以继续优化。我们仔细观察该转移方程，不难发现其相当于是在区间 k\in[i-1, j-1] 中找了一个最大的 f(i-1, k)。

因此，我们可以考虑进行 前缀和 （前缀最大值）优化，将这个最大的 f(i - 1, k) 通过一个前缀最大值数组 g(i - 1, j) 存起来。

即，g(i - 1, j) 表示 k\in[0, j] 中最大的 f(i - 1, k) 的值。可以得到 g(i, j) 的状态转移方程：

g(i, j) = \max\{g(i, j - 1), f(i, j)\}

由于 f 的转移方程中，k 的下界为 i-1，为了防止 g 从非法的状态转移，我们还需要将非法的 f 状态设置为负无穷，这样就能够保证 g 不会从非法的 k 值转移过来了。整体的状态转移方程如下：

\begin{cases} f(i, j) = g(i - 1, j - 1) + a_{i, j} \\ g(i, j) = \max\{g(i, j - 1), f(i, j)\} \end{cases}

复杂度是 O(FV)。

方案二

从方案二状态的定义，我们可以很轻松地列出两种条件下的前置状态：

假设当前要计算 f(i, j)，考虑其前置状态

  1. 第 i 束花放在第 j 个花瓶，则前 i-1 束花可放在前 j-1 个花瓶： f(i - 1, j - 1) + a_{i,j}\to f(i, j)
  2. 第 i 束花不放在第 j 个花瓶，则前 i-1 束花可放在前 j 个花瓶： f(i - 1, j) \to f(i, j)

因此，容易列出转移方程：

f(i, j) = \max\{f(i-1, j-1) + a_{i,j}, f(i-1,j)\}

复杂度为 O(FV)

此时还有一个问题，因为该状态的定义没有强制要求第 i 束花一定会放在某个花瓶中（不同于方案一），会不会导致第 i 束花没有放在任何一个花瓶中，违反了题目条件？

答案是不会，原因留给读者自行思考。(tips: 可以考虑状态的边界条件)

下面呈上方案二的代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1005, INF = 1e9 + 7;
int f[maxn][maxn], a[maxn][maxn], n, m;
pair<int, int> from[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> a[i][j];

    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            f[i][j] = -INF;

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

    for(int i = 1; i <= n; i ++) {
        for(int j = i; j <= m; j ++) {
            int s1 = f[i - 1][j - 1] + a[i][j], s2 = f[i][j - 1];
            if(s1 >= s2) {
                f[i][j] = s1;
                from[i][j] = {i - 1, j - 1};
            } else {
                f[i][j] = s2;
                from[i][j] = {i, j - 1};
            }
        }
    }

    cout << f[n][m] << '\n';
    vector<int> path(n + 1);
    for(int i = n, j = m; i > 0;) {
        int pre_i = from[i][j].first, pre_j = from[i][j].second;
        if(pre_i == i - 1) path[i] = j;
        i = pre_i, j = pre_j;
    }
    for(int i = 1; i <= n; i ++)
        cout << path[i] << " \n"[i == n];
    return 0;
}