花店橱窗

形式化题目

给定 $F$ 朵花和 $V$ 个花瓶（ $1 \leqslant F \leqslant V \leqslant 100$ ），以及矩阵 $a$ ：第 $i$ 朵花放进第 $j$ 个花瓶的美观值为 $a_{i,j}$ （可正可负）。要求选出花瓶下标 $j_1 < j_2 < \cdots < j_F$ ，最大化

\sum_{i=1}^{F} a_{i,\,j_i}

输出这个最大值，以及一组取到最大值的下标；若有多组方案，输出字典序最小的一组（即让 $j_1$ 尽量小，其次 $j_2$ 尽量小，依此类推）。

正解

思路

从朴素到线性 DP。 最直接的想法是给每朵花枚举花瓶，复杂度是指数级。但注意题目自带"顺序"：花必须按 $1,2,\dots,F$ 的顺序放进编号递增的花瓶。这意味着决策是分阶段的——前 $i$ 朵花怎么放，只影响"第 $i$ 朵花放在哪个花瓶"这一个信息，与更早的具体位置无关。这正是线性 DP 的信号。

状态与转移。 设

dp[i][j] = \text{前 } i \text{ 朵花都放好且第 } i \text{ 朵放在花瓶 } j \text{ 时的最大美观值}

第 $i$ 朵花放在 $j$ 时，第 $i-1$ 朵花必须放在某个 $k < j$ ，所以

dp[i][j] = a_{i,j} + \max_{k<j} dp[i-1][k]

$\max_{k<j}$ 随 $j$ 右移只会扩大候选集合，用滚动的前缀最大值维护即可把整层转移压到 $O(V)$ ，总复杂度 $O(FV)$ 。答案为 $\max_j dp[F][j]$ 。

还原字典序最小的方案。 直接用正向 dp 倒推 pre 数组会比较繁琐。更优雅的做法是把 dp 反过来算一遍——定义后缀状态

g[i][j] = \text{第 } i, i+1, \dots, F \text{ 朵花放进花瓶 } j, j+1, \dots, V \text{ 的最大美观值}

转移只有两个选择：第 $i$ 朵花放 $j$ ，或者跳过花瓶 $j$ ：

g[i][j] = \max\bigl(\,a_{i,j} + g[i+1][j+1],\;\; g[i][j+1]\,\bigr)

边界 $g[F+1][*] = 0$ （没有花了，任何起点都是 0）。花瓶下标越界的位置不可行，保持 $-\infty$ ：比如第 1 朵花若放在花瓶 4，剩下的 $F-1$ 朵花就不够花瓶用了，这类状态天然取不到有限值。隐式约束 $j_i \geqslant i$ （前面 $i-1$ 朵花至少要占 $i-1$ 个花瓶）则由贪心的单调性自动保证。

有了 $g$ ，从第 1 朵花开始贪心：第 $i$ 朵花从当前下界 $j$ （初值 1）开始向右扫，找到第一个满足

a_{i,j} + g[i+1][j+1] = g[i][j]

的花瓶——等式成立说明"第 $i$ 朵放 $j$ "这条路能取到剩余部分的最优值，不损失任何总值；取最小的这样的 $j$ 就保证了字典序最小。放好后 $j \leftarrow j+1$ ，继续下一朵花。

看样例。对样例数据算出后缀表 $g$ （ $-\infty$ 表示该位置不可行，如剩余花不够分配）：

$g[i][j]$	$j=1$	$j=2$	$j=3$	$j=4$	$j=5$
$i=1$	53	53	25	$-\infty$	$-\infty$
$i=2$	41	41	30	30	$-\infty$
$i=3$	20	20	20	20	20
$i=4$ （边界）	0	0	0	0	0

观察重点：

第一行 $g[1][1] = 53$ 就是答案； $i=1$ 、 $j=4,5$ 为 $-\infty$ ，因为后面的花瓶不够后面两朵花分。
第 3 行全是 20：只剩一朵花时它可以跳过前面任意花瓶、挑最好的花瓶 5（ $a_{3,5}=20$ ），所以每个起点都同样优。
从左上角 53 出发，每一步要么"放在这里"（斜向右下，吃掉 $a_{i,j}$ ），要么"跳过这个花瓶"（向右一格），53 就是这条路径上各 $a$ 值之和的最大者。

贪心逐朵还原的过程：

花朵 $i$	从 $j$ 起扫到的位置	判定 $a_{i,j}+g[i+1][j+1] = g[i][j]$	决策
1	$j=2$	$j=1$ ： $7+41=48 \neq 53$ ； $j=2$ ： $23+30=53$ ✓	放花瓶 2
2	$j=4$	$j=3$ ： $-4+20=16 \neq 30$ ； $j=4$ ： $10+20=30$ ✓	放花瓶 4
3	$j=5$	$20+0=20 = g[3][5]$ ✓	放花瓶 5

每朵花都取"能取到最优值的最早花瓶"，得到字典序最小方案 2 4 5。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 花店橱窗布置：后缀 DP + 贪心还原字典序最小方案
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXF = 512;
const int MAXV = 512;
const ll NEG = -(1LL << 50); // 不可行状态哨兵

ll a[MAXF][MAXV]; // a[i][j]：第 i 朵花放进第 j 个花瓶的美观度（均 1 起编号）
// g[i][j]：第 i..F 朵花放进花瓶 j..V 的最大美观度（后缀 DP）
ll g[MAXF][MAXV];
ll pos[MAXF]; // 还原出来的方案：第 i 朵花的花瓶编号

int main() {
    int f, v;
    if (scanf("%d %d", &f, &v) != 2) {
        return 0;
    }
    for (int i = 1; i <= f; i++) {
        for (int j = 1; j <= v; j++) {
            scanf("%lld", &a[i][j]);
        }
    }
    for (int i = 1; i <= f + 1; i++) {
        for (int j = 0; j <= v + 2; j++) {
            g[i][j] = NEG;
        }
    }
    for (int j = 0; j <= v + 2; j++) {
        g[f + 1][j] = 0; // 没有花要放：任何花瓶区间都是 0
    }

    for (int i = f; i >= 1; i--) {
        // 第 i 朵花放 j 时前面还剩 i-1 朵花，所以 j 至少是 v-f+i
        for (int j = v - f + i; j >= 1; j--) {
            g[i][j] = max(a[i][j] + g[i + 1][j + 1], g[i][j + 1]);
        }
    }

    // 贪心还原字典序最小方案：第 i 朵花取最小的花瓶 j，使得「放 j + 后缀最优」仍等于整体最优
    int j = 1;
    for (int i = 1; i <= f; i++) {
        while (j <= v && a[i][j] + g[i + 1][j + 1] != g[i][j]) {
            j++;
        }
        pos[i] = j;
        j++;
    }

    printf("%lld\n", g[1][1]);
    for (int i = 1; i <= f; i++) {
        if (i > 1) printf(" ");
        printf("%lld", pos[i]);
    }
    printf("\n");
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 21:57
# update_at: 2026-10-01 21:57

import sys

NEG = -10**100  # 不可行状态哨兵：花比可用花瓶还多时的空方案


def suffix_best(a: list[list[int]]) -> list[list[int]]:
    """g[i][j] = 第 i..F 朵花放进花瓶 j..V 的最大美观度（后缀 DP，用于贪心还原方案）。"""
    f, v = len(a), len(a[0])
    g = [[NEG] * (v + 2) for _ in range(f + 2)]
    g[f + 1] = [0] * (v + 2)  # 没有花要放：任何花瓶区间都是 0
    for i in range(f, 0, -1):
        # 第 i 朵花放 j 时，前面还剩 i-1 朵花，所以 j 至少是 i
        for j in range(v - f + i, 0, -1):
            g[i][j] = max(a[i - 1][j - 1] + g[i + 1][j + 1], g[i][j + 1])
    return g


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    f, v = next(data), next(data)
    a = [[next(data) for _ in range(v)] for _ in range(f)]

    g = suffix_best(a)

    # 贪心还原字典序最小方案：第 i 朵花取最小的花瓶 j，
    # 使得「放 j + 后缀最优」仍等于整体最优 g[i][j]
    j = 1
    pos = []
    for i in range(1, f + 1):
        while a[i - 1][j - 1] + g[i + 1][j + 1] != g[i][j]:
            j += 1
        pos.append(j)
        j += 1

    print(g[1][1])
    print(*pos)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(FV)$ ——后缀表 $FV$ 个状态，每个 $O(1)$ 转移；贪心还原每朵花至多扫 $V$ 个花瓶，也是 $O(FV)$ 。 $F, V \leqslant 100$ ，总量约 $10^4$ 。
空间复杂度： $O(FV)$ 存后缀表 $g$ 。
实测：真实测试数据 20 组全部通过，单组约 0.02 s、峰值内存约 15 MB，远低于 1 s / 128 MB 限制。

总结

花按固定顺序放、位置必须递增 → "前 $i$ 朵花 + 第 $i$ 朵的位置"就是完整状态，天然适合线性 DP， $O(FV)$ 。
$\max_{k<j}$ 型转移用滚动前缀最大值优化，是"线性 DP + 前缀最值"的标准套路。
输出字典序最小方案的关键技巧：把 dp 反向后缀化，使"每一步取最早可行位置"成为合法贪心；判定条件是 a[i][j] + g[i+1][j+1] == g[i][j]。

目录

形式化题目

正解

思路

代码

复杂度

总结