【例9.23】橱窗布置(flower)

GitHub跳转原题关系图返回列表

把“上一束花落在哪个花瓶”压成前缀最大值 g[i][t]，用 O(FV) 线性 DP 求最大美学值，再逐层取最靠左的最优落点回溯出严格递增的摆放方案。

OJ: roj

题目 ID: 1279

难度:普及-

标签:普及-动态规划线性DP前缀最大值回溯python

创建: 2026-09-30 03:02

更新: 2026-10-05 07:51

题目描述

橱窗里从左到右摆着编号 $1$ 到 $V$ 的花瓶，要放入 $F$ 束花，花束 $i$ 放进花瓶 $j$ 的美学值为 $A_{ij}$ （空花瓶美学值为 $0$ ）；必须保持花束编号的顺序（ $i<j$ 时花束 $i$ 要放在花束 $j$ 左边的花瓶里），求总美学值最大的摆放方式，最优方案不唯一时输出任意一种。输入第一行为 $F, V$ ，随后 $F$ 行每行 $V$ 个整数给出 $A_{ij}$ ；输出第一行为最大美学值，第二行为 $F$ 个整数，第 $K$ 个数表示花束 $K$ 所在的花瓶编号。数据范围： $1\leqslant F\leqslant 100$ ， $F\leqslant V\leqslant 100$ ， $-50\leqslant A_{ij}\leqslant 50$ 。样例：输入依次为 3 5 / 7 23 -5 -24 16 / 5 21 -4 10 23 / -21 5 -4 -20 20，输出依次为 53 / 2 4 5。

思路

设 $g[i][t]$ 为花束 $1..i$ 依次放进编号不超过 $t$ 的花瓶能取得的最大美学值，转移 $g[i][t]=\max(g[i][t-1],\ g[i-1][t-1]+A_{i,t})$ ：花瓶 $t$ 要么空着，要么插第 $i$ 束花， $t<i$ 时为 $-\infty$ ，答案即 $g[F][V]$ ，总复杂度 $O(FV)$ 。还原方案时从右往左逐层处理：利用 $g[i]$ 沿 $t$ 单调不减的性质，每层取最靠左、又取到该层目标值的位置——由最小性可知该位置必来自“插花”那一支，于是第 $i$ 束花落定、目标值换成 $g[i-1][pos-1]$ ，得到的编号天然严格递增。

参考代码

Python 版：

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
48
49
50
51
52#!/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-09-30 03:03
# update_at: 2026-09-30 03:13

import sys
from bisect import bisect_left

NEG = -10**9  # 美学值总和最小也只有 -50*100，用它表示“这些花束装不下”


def prefix_levels(v: int, a: list[list[int]]) -> list[list[int]]:
    """levels[i][t]：花束 1..i 依次放进编号不超过 t 的花瓶时的最大美学值。

    只存前缀最大值即可：第 i 束花定在花瓶 t 时，前 i-1 束花只要全部挤在 t 左侧，
    具体占哪几个花瓶不影响后面的选择，于是“最后一束花放在哪”这一维被压掉了。
    """
    levels = [[0] * (v + 1)]  # 第 0 层：没有花束，任何花瓶前缀的美学值都是 0
    for i, row in enumerate(a, 1):
        prev, cur = levels[-1], [NEG] * (v + 1)
        for t in range(i, v + 1):  # 不足 i 个花瓶放不下 i 束花，保持 NEG
            cur[t] = max(cur[t - 1], prev[t - 1] + row[t - 1])  # 花瓶 t 空着 / 插第 i 束花
        levels.append(cur)
    return levels


def used_vases(f: int, v: int, levels: list[list[int]]) -> list[int]:
    """从右往左回溯：每束花都取“最靠左、又能拼出该层最优值”的花瓶。"""
    pick, target, limit = [0] * f, levels[f][v], v + 1
    for i in range(f, 0, -1):
        pos = bisect_left(levels[i], target, i, limit)  # 该层前缀值第一次达到 target 的花瓶
        pick[i - 1] = pos
        if i > 1:
            # 第 i 束花占了 pos，前 i-1 束花的目标值就是它们在前 pos-1 个花瓶里的最优值
            target, limit = levels[i - 1][pos - 1], pos
    return pick


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)]  # a[i][j]：花束 i+1 放花瓶 j+1 的美学值

    levels = prefix_levels(v, a)
    print(levels[f][v])
    print(*used_vases(f, v, levels))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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// main.cpp：O(FV) 线性 DP 求最大美学值，再逐层回溯输出方案。
/**
 * 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-05 07:51
 * update_at: 2026-10-05 07:51
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 105;
const ll NEG = -1e9; // 表示“用前 t 个花瓶放不下 i 束花”

int f, v;
int a[MAXN][MAXN]; // a[i][j]：花束 i 放进花瓶 j 的美学值
ll g[MAXN][MAXN];  // g[i][t]：花束 1..i 依次放进编号不超过 t 的花瓶的最大美学值
int pick[MAXN];    // pick[i]：第 i 束花选的花瓶编号

// 填前缀最大值表：花瓶 t 要么空着（g[i][t-1]），要么插第 i 束花（g[i-1][t-1]+a[i][t]）
void solve() {
    for (int t = 0; t <= v; ++t)
        g[0][t] = 0; // 没有花束时美学值为 0
    for (int i = 1; i <= f; ++i) {
        g[i][i - 1] = NEG; // 不足 i 个花瓶放不下 i 束花
        for (int t = i; t <= v; ++t) {
            ll best = g[i][t - 1]; // 花瓶 t 空着
            if (g[i - 1][t - 1] + a[i][t] > best)
                best = g[i - 1][t - 1] + a[i][t]; // 花瓶 t 插第 i 束花
            g[i][t] = best;
        }
    }

    // 从右往左回溯：g[i] 逐层单调不减，取最靠左、又取到该层目标值的花瓶，
    // 这个位置一定来自“插花”那一支，编号天然严格递增；
    // t < i 时 g[i][t] = NEG，不会误配，循环必然停在 [i, v] 内
    ll target = g[f][v];
    for (int i = f; i >= 1; --i) {
        int pos = i; // 第一个取到 target 的位置，必有 g[i][pos] == target
        while (g[i][pos] < target)
            ++pos;
        pick[i] = pos;
        target = g[i - 1][pos - 1]; // 前 i-1 束花的目标值
    }

    printf("%lld\n", g[f][v]);
    for (int i = 1; i <= f; ++i)
        printf("%d%c", pick[i], i == f ? '\n' : ' ');
}

int main() {
    scanf("%d %d", &f, &v);
    for (int i = 1; i <= f; ++i)
        for (int j = 1; j <= v; ++j)
            scanf("%d", &a[i][j]);
    solve();
    return 0;
}

【题目描述】

假设以最美观的方式布置花店的橱窗，有 $F$ 束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从 $1$ 到 $V$ 顺序编号， $V$ 是花瓶的数目，编号为 $1$ 的花瓶在最左边，编号为 $V$ 的花瓶在最右边，花束可以移动，并且每束花用 $1$ 到 $F$ 的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果 $i < j$ ，则花束 $i$ 必须放在花束 $j$ 左边的花瓶中。

例如，假设杜鹃花的标识数为 $1$ ，秋海棠的标识数为 $2$ ，康乃馨的标识数为 $3$ ，所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。

每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为 $0$ 。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。

根据表格，杜鹃花放在花瓶 $2$ 中，会显得非常好看，但若放在花瓶 $4$ 中则显得很难看。

为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件： $1≤F≤100$ ， $F≤V≤100$ ， $-50≤A\_{ij}≤50$ ，其中 $A\_{ij}$ 是花束 $i$ 摆放在花瓶 $j$ 中的美学值。输入整数 $F$ ， $V$ 和矩阵 $(A\_{ij})$ ，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。

花瓶1

花瓶2

花瓶3

花瓶4

花瓶5

杜鹃花

-5

-24

秋海棠

-4

康乃馨

-21

-4

-20

假设条件:

$1 \leq F \leq100 $，其中 $F$ 为花束的数量，花束编号从 $1$ 至 $F$ 。

$F ≤ V ≤100$ ，其中 $V$ 是花瓶的数量。

$-50 ≤ A\_{ij} ≤ 50 $，其中 $A\_{ij}$ 是花束 $i$ 在花瓶 $j$ 中的美学值。

【输入】

第一行包含两个数： $F，V$ 。

随后的 $F$ 行中，每行包含 $V$ 个整数， $A\_{ij}$ 即为输入文件中第（ $i+1$ ）行中的第 $j$ 个数。

【输出】

第一行是程序所产生摆放方式的美学值。

第二行必须用 $F$ 个数表示摆放方式，即该行的第 $K$ 个数表示花束K所在的花瓶的编号。

【输入样例】

text

1
2
3
4
53 5 
7 23 –5 –24 16
5 21 -4 10 23
-21 5 -4 -20 20

【输出样例】

text

【来源】

一本通在线评测