自动搬运

查看原文

来自洛谷，原作者为

	Godのfather SMILE BACK

搬运于2025-08-24 21:31:06，当前版本为作者最后更新于2018-04-26 14:08:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不一样的动态规划

update on 2025.6.18

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

---

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

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

状态定义

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

1. $f(i, j)$ 表示第 $i$ 束花放在第 $j$ 个花瓶的最大美学值。
2. $f(i, j)$ 表示第 $i$ 束花放不放在第 $j$ 个花瓶的最大美学值（从放和不放两种状态中取一个最大的）。

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

如果你觉得 方案二 更简单，那么恭喜你，你的直觉是对的。无论是代码实现，抑或是时间复杂度（在不对转移方程进行优化的情况下），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;
}