[IOI 1999] 花店橱窗布置

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

线性 DP + 方案还原: dp[i][j] 表示前 i 束花放入前 j 个花瓶的最大美学值, 按放或不放转移, 再反向还原出递增方案.

OJ: luogu

题目 ID: P1854

难度:普及

标签:动态规划线性DP方案还原c++python

创建: 2026-10-26 14:01

更新: 2026-10-26 16:36

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定 F×VF \times V 矩阵 ai,ja_{i,j}, 从第 ii 行各选一个位置 pip_i, 满足 1≤p1<p2<⋯<pF≤V1 \le p_1 < p_2 < \dots < p_F \le V, 最大化 ∑i=1Fai,pi\sum_{i=1}^{F} a_{i,p_i}. 输出最大值和任意一组达到最大值的递增位置序列.

正解

思路

花束按编号顺序摆放, 等价于在矩阵里从左到右选一条递增下标序列. 只看前 ii 束花和前 jj 个花瓶, 花瓶 jj 只有两种选择: 不放花束 ii, 或放花束 ii.

  • 不放: 问题变成前 ii 束花放入前 j−1j-1 个花瓶, 值 dp[i][j-1].
  • 放: 花束 ii 占花瓶 jj, 前面 i−1i-1 束花只能放前 j−1j-1 个花瓶, 值 dp[i-1][j-1] + a[i][j].

于是 dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + a[i][j]). 初始 dp[0][j] = 0, 其余负无穷, 答案 dp[F][V].

下面用样例 a=[[7,23,−5,−24,16],[5,21,−4,10,23],[−21,5,−4,−20,20]]a = [[7,23,-5,-24,16],[5,21,-4,10,23],[-21,5,-4,-20,20]] 填表, 观察 dp[i][j] 的变化:

i \ j 0 1 2 3 4 5
0 0 0 0 0 0 0
1 -inf 7 23 23 23 23
2 -inf -inf 28 28 33 46
3 -inf -inf -inf 24 24 53

表前看三点: dp[0][j] 恒为 0, j < i 的格子保持负无穷(不可达), 每一行从左到右不降. 表后看: dp[3][5] = 53 是答案; 第一行从左到右的最大值 23 说明花束 1 最优放花瓶 2.

方案还原从 (F, V) 往回走: 若 dp[i][j] == dp[i][j-1], 说明最优解没用到花瓶 jj, 左移一位; 否则花束 ii 必须放花瓶 jj, 记录 jj 后向左上走一格. 这样每次记录都对应一次"放花束"的真实转移, 记录序列从后往前递减, 倒序输出就得到严格递增的方案.

代码

cpp
/**
 * 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-26 13:36
 * update_at: 2026-10-26 16:36
 */
// main.cpp: 正式主解. dp[i][j] = 前 i 束花放入前 j 个花瓶的最大美学值.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 105;      // F, V 都不超过 100
const ll NEG = -(1LL << 60);  // 负无穷哨兵: 美学值最小为 -50*100, 远大于 NEG

ll F, V;                     // F 束花, V 个花瓶
ll a[MAXN][MAXN];            // a[i][j]: 花束 i 放入花瓶 j 的美学值
ll dp[MAXN][MAXN];           // dp[i][j]: 前 i 束花放入前 j 个花瓶的最大美学值
ll path[MAXN];               // path[t]: 还原方案时从后往前记录的花瓶编号

void read_data() {
    cin >> F >> V;
    for (int i = 1; i <= F; i++) {
        for (int j = 1; j <= V; j++) {
            cin >> a[i][j];
        }
    }
}

void solve() {
    // 初始化: 0 束花放入任意多个花瓶美学值为 0; 其余状态置为负无穷.
    for (int i = 0; i <= F; i++) {
        for (int j = 0; j <= V; j++) {
            dp[i][j] = NEG;
        }
    }
    for (int j = 0; j <= V; j++) {
        dp[0][j] = 0;
    }

    // 转移: 花束 i 不放花瓶 j -> dp[i][j-1]; 放 -> dp[i-1][j-1] + a[i][j].
    for (int i = 1; i <= F; i++) {
        for (int j = i; j <= V; j++) {
            ll not_use = dp[i][j - 1];
            ll use = dp[i - 1][j - 1] + a[i][j];
            dp[i][j] = max(not_use, use);
        }
    }

    cout << dp[F][V] << "\n";

    // 方案还原: 从 (F, V) 反推. 若 dp[i][j] == dp[i][j-1], 说明最优解没用花瓶 j,
    // 左移; 否则花束 i 一定放在花瓶 j, 记录后向左上角走一步.
    ll i = F;
    ll j = V;
    ll cnt = 0;
    while (i > 0) {
        if (j > i && dp[i][j] == dp[i][j - 1]) {
            j--;
        } else {
            path[++cnt] = j;
            i--;
            j--;
        }
    }

    // path 是逆序记录的, 倒序输出得到递增序列.
    for (int k = cnt; k >= 1; k--) {
        cout << path[k] << (k == 1 ? '\n' : ' ');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_data();
    solve();

    return 0;
}
py
#!/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-26 13:36
# update_at: 2026-10-26 13:36

import sys

NEG = -10**18  # 负无穷哨兵: 表示 dp 状态不可达


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    f = next(data)  # 花束数
    v = next(data)  # 花瓶数
    # a[i][j]: 花束 i 放入花瓶 j 的美学值, 下标从 1 开始.
    a = [[0] * (v + 1)] + [[0] + [next(data) for _ in range(v)] for _ in range(f)]

    # dp[i][j]: 前 i 束花放入前 j 个花瓶(每瓶至多一束)的最大美学值.
    dp = [[NEG] * (v + 1) for _ in range(f + 1)]
    dp[0] = [0] * (v + 1)
    for i in range(1, f + 1):
        for j in range(i, v + 1):
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + a[i][j])

    # 从 (f, v) 反推方案: 不取花瓶 j 就左移, 否则花束 i 放花瓶 j, 向左上走.
    plan: list[int] = []
    i, j = f, v
    while i > 0:
        if j > i and dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            plan.append(j)
            i -= 1
            j -= 1

    print(dp[f][v])
    print(" ".join(map(str, plan[::-1])))


if __name__ == "__main__":
    solve()

复杂度

  • 时间复杂度: O(FV)O(FV), 填表 F×VF \times V 个状态, 每个状态 O(1)O(1), 方案还原 O(F+V)O(F+V).
  • 空间复杂度: O(FV)O(FV).

总结

本题把"花束顺序对应花瓶编号递增"的约束直接写进 DP 状态, 用"放或不放当前花瓶"的二选一转移消除组合枚举. 方案不唯一, 还原时只要始终沿真实转移反推, 就能得到一组合法递增方案.