成绩单

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

把最后被取走的一批当作区间骨架,其余元素被它切成互相独立的空隙;用 g[l][r][x][y] 记「留下含 l 的一批、其分数排名夹在 [x,y] 内」的代价,区间 DP 即可。

OJ: roj

题目 ID: 1766

难度:提高+/省选-

标签:动态规划区间DPpython

创建: 2026-10-08 00:39

更新: 2026-10-08 00:39

形式化题目

nn 份成绩单按编号 1∼n1 \sim n 叠成一叠,第 ii 张的分数是 wiw_i。一次操作从当前这一叠 中抽取连续的一段发掉,剩下的部分按原顺序自动拼成新的一叠,如此反复直到发完。 若一共发了 kk 批,第 ii 批的分数最大值、最小值分别为 maximax_i、minimin_i,则方案代价为

a⋅k+b⋅∑i=1k(maxi−mini)2, a\cdot k + b\cdot \sum_{i=1}^{k} (max_i - min_i)^2 ,

要求最小化代价。数据范围:n≤50n \le 50,a≤100a \le 100,b≤10b \le 10,wi≤1000w_i \le 1000。

注意"抽取连续的一段"限定的是当前那一叠里的连续段,而不是原序列上的连续区间: 中间的元素被先抽走后,它左右两侧在剩下的那一叠里就相邻了,于是可以并进同一批。 这一点是本题的分水岭 —— 若误以为"每一批都是原序列上的连续区间",问题退化成 fi=min⁡j(fj−1+a+b(max⁡j..iw−min⁡j..iw)2)f_i = \min_j \big(f_{j-1} + a + b(\max_{j..i} w - \min_{j..i} w)^2\big) 的线性 DP, 在题面样例上会算出 2121,而正确答案是 1515。

样例 w=(7,10,9,10,6,7,10,7,1,2)w = (7,10,9,10,6,7,10,7,1,2),a=3a=3、b=1b=1 的一个最优方案是

批次 取走的元素(按原序列位置) 分数 极差 代价
1 2, 3, 4 10, 9, 10 1 4
2 7 10 0 3
3 1, 5, 6, 8 7, 6, 7, 7 1 4
4 9, 10 1, 2 1 4

第 3 批在原序列上占位置 1,5,6,81,5,6,8,看起来"断成三截";但在第 1、2 批(位置 2,3,4,72,3,4,7) 被取走之后,这四张成绩单在剩下的那一叠里恰好是连续的。代价合计 4+3+4+4=154+3+4+4=15。

正解

思路

先给"一批合法"下一个只看位置的刻画。 给每张成绩单赋一个批次时间 tt(同一批时间相同, 不同批不同)。设某批 BB 的元素在原序列中最左、最右位置为 L,RL,R,那么

B 在被取走的那一刻合法  ⟺  ∀p,  L<p<R  ∧  p∉B  ⇒  tp<tB. B \text{ 在被取走的那一刻合法} \iff \forall p,\; L < p < R \;\wedge\; p \notin B \;\Rightarrow\; t_p < t_B .

必要性:若这样的 pp 还没被取走,取 BB 时它正夹在 BB 的最左与最右元素之间,BB 在这一叠里不连续。 充分性:若这样的 pp 都已取走,BB 的元素在那一叠里恰好排成一个连续段。

判定条件里只出现位置,分数只通过 (max−min)2(max-min)^2 影响代价 —— 这一点决定了状态里只需要记分数的 极值,不需要记位置。

朴素做法与瓶颈。 枚举每一轮取哪一段,状态随轮数指数爆炸(n=50n=50 时不可行); 而"把 [l,r][l,r] 拆成两个独立子区间"的普通区间 DP 又漏掉了最关键的情形:[l,r][l,r] 中间的一部分先被 取空,使 wlw_l 与 wrw_r 拼接在一起、最后同批取走。只有 f(l,r)f(l,r) 一个数,表达不出"区间里还留着 一部分元素、这批元素未来的极差是多少"。

关键观察:以"最后一批"为骨架。 对区间 [l,r][l,r],设 SS 是其中最后被取走的那一批。 SS 取走时 [l,r][l,r] 内其余元素都已取走,所以 SS 必然合法;反过来,任取一个非空 S⊆[l,r]S \subseteq [l,r], 让 [l,r]∖S[l,r]\setminus S 的元素先按某个顺序取空、最后取 SS,SS 也是合法的。更关键的是:

[l,r]∖S[l,r]\setminus S 中的每一批,其元素必整体落在 SS 在 [l,r][l,r] 内相邻两个位置之间的 空隙(极大连续段)里。

否则某批 BB 的元素跨过了 SS 的某个元素 qq,即 qq 夹在 BB 的最左与最右元素之间且 q∉Bq \notin B; 但 BB 比 SS 早取走(SS 是最后一批),与上一段的刻画矛盾。于是各空隙是互相独立的子问题:

dp[l][r]=min⁡S≠∅(a+b (max⁡S−min⁡S)2+∑空隙dp[空隙]). dp[l][r] = \min_{S \ne \varnothing} \Big( a + b\,(\max S - \min S)^2 + \sum_{\text{空隙}} dp[\text{空隙}] \Big).

状态。 空隙的划分只取决于"留下哪些位置",而留下的那批元素未来的代价只取决于它的 分数极值。把分数离散化(V≤n≤50V \le n \le 50 个不同分数,排名 0∼V−10 \sim V-1,val[x]val[x] 为排名 xx 的原分数), 定义

  • dp[l][r]dp[l][r]:把区间 [l,r][l,r] 当成独立的一叠全部发完的最小代价(空区间为 00);
  • g[l][r][x][y]g[l][r][x][y]:把 [l,r][l,r] 中"不属于最后一批"的元素全部消掉的最小代价,要求最后一批含位置 ll (用它去重:ll 不属于最后一批时,ll 必然落在某个更小的空隙里,那属于下一种枚举), 且其中所有分数的排名都落在 [x,y][x,y] 内;这个状态不含最后一批自身的代价;
  • hh[s][r]hh[s][r]:[s,r][s,r] 中 ss 作为最后一批最左元素时的最优总代价(已经结算过最后一批)。

转移。 按区间长度从小到大递推。固定 [l,r][l,r] 后:

第一步,枚举分割点 kk(l≤k<rl \le k < r),左半留下含 ll 的一批,右半两种选择:

g[l][r][x][y]=min⁡k=lr−1(g[l][k][x][y]+min⁡(dp[k+1][r],  [ rankk+1∈[x,y] ]⋅g[k+1][r][x][y])), g[l][r][x][y] = \min_{k=l}^{r-1} \Big( g[l][k][x][y] + \min\big(dp[k+1][r],\; [\,rank_{k+1} \in [x,y]\,]\cdot g[k+1][r][x][y]\big) \Big),

即右半要么整段先取空(代价 dp[k+1][r]dp[k+1][r]),要么也留下含 k+1k+1 的一批、并进同一个最后一批 (此时必须 rankk+1∈[x,y]rank_{k+1} \in [x,y])。基态是长度 11:g[l][l][x][y]=0g[l][l][x][y] = 0(当且仅当 x≤rankl≤yx \le rank_l \le y, 否则为 ∞\infty),因为"只留下 ll 自己"不需要先消掉任何元素。

第二步,结算最后一批。枚举它的排名上下界(必然夹住 ranklrank_l):

hh[l][r]=min⁡x≤rankl≤y(g[l][r][x][y]+a+b (val[y]−val[x])2). hh[l][r] = \min_{x \le rank_l \le y} \Big( g[l][r][x][y] + a + b\,(val[y]-val[x])^2 \Big).

这里用的是 val[y]−val[x]val[y]-val[x] 而不是真实的极差:对固定的 gg 取值,把区间收紧到"恰好等于实际留下的 那批元素的极值"只会让代价更小,而这样的 (x,y)(x,y) 一定也在枚举范围内,所以取 min⁡\min 之后结果正确。

第三步,dp[l][r]dp[l][r] 枚举最后一批的最左位置 ss,[l,s−1][l,s-1] 是 ss 左边的空隙:

dp[l][r]=min⁡s=lr(dp[l][s−1]+hh[s][r]),dp[l][l−1]=0. dp[l][r] = \min_{s=l}^{r} \Big( dp[l][s-1] + hh[s][r] \Big), \qquad dp[l][l-1] = 0 .

答案是 dp[1][n]dp[1][n]。

为什么这样不重不漏。 设最优方案在 [l,r][l,r] 上的最后一批为 SS,最左元素位置为 ss。则 [l,s−1][l,s-1] 是一个空隙(代价 dp[l][s−1]dp[l][s-1],SS 与它互不影响),而 [s,r][s,r] 上的其余元素都被切成空隙, 代价正是 g[s][r][x∗][y∗]g[s][r][x^*][y^*]((x∗,y∗)(x^*,y^*) 取 SS 的真实极值),于是 dp[l][r]≤dp[l][r] \le 最优值; 反过来,转移里每一个组合都对应一个能排出取走顺序的合法方案(先按空隙递归取空、最后取 SS), 所以 dp[l][r]≥dp[l][r] \ge 最优值。

代码

Python 版:

python
#!/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-08 00:39
# update_at: 2026-10-08 00:39

import sys
from bisect import bisect_left

INF = 10 ** 9  # 无穷大:合法答案 < 5e8,与合法值相加也不会被误判(Python 整数不溢出)


def min_cost(w: list[int], a: int, b: int) -> int:
    """区间 DP:返回把整叠成绩单按批次全部发完的最小代价。

    一批不要求是原序列上的连续区间:设 S 为区间 [l,r] 里最后被取走的那批,则
    [l,r] 中不属于 S 的元素被 S 切成互不相干的空隙,每个空隙是独立的子问题。
    状态:
      dp[l][r]        把 [l,r] 当成独立一叠全部发完的最小代价(空区间为 0)
      G[l][r][x*V+y]  消掉 [l,r] 中不属于最后一批的元素的最小代价,要求最后一批
                      含位置 l、其分数排名落在 [x,y] 内(不含最后一批自身的代价)
      hh[s][r]        [s,r] 中 s 作为最后一批最左元素时的最优总代价
    """
    n = len(w)
    vals = sorted(set(w))
    V = len(vals)
    rank = [bisect_left(vals, x) for x in w]  # 位置 -> 压缩排名;原分数只用于算极差

    # 位置 l 若属于最后一批,则该批的排名区间 [x,y] 必须夹住 rank[l]。
    # pairs[l] 列出这些区间,idx[l] 是它们在 V*V 扁平表里的下标 x*V+y。
    pairs = [[(x, y) for x in range(rk + 1) for y in range(rk, V)] for rk in rank]
    idx = [[x * V + y for x, y in ps] for ps in pairs]

    dp = [[0] * n for _ in range(n + 1)]
    hh = [[INF] * n for _ in range(n)]
    G: list[list[list[int]]] = [[[] for _ in range(n)] for _ in range(n)]

    for length in range(1, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1
            ps, ids = pairs[l], idx[l]
            cur = [INF] * (V * V)  # 排名不夹住 rank[l] 的组合永远保持 INF

            if length == 1:
                for i in ids:
                    cur[i] = 0  # 只留下 l 自己,不必先消掉任何元素
            else:
                for t, (x, y) in enumerate(ps):
                    i = ids[t]
                    best = INF
                    for k in range(l, r):
                        left = G[l][k][i]
                        if left >= INF:
                            continue
                        rk1 = rank[k + 1]
                        right = dp[k + 1][r]  # 右半 [k+1,r] 整段先取空
                        if x <= rk1 <= y:  # 右半也留下含 k+1 的一批,并入同一个最后一批
                            gv = G[k + 1][r][i]
                            if gv < right:
                                right = gv
                        cand = left + right
                        if cand < best:
                            best = cand
                    cur[i] = best
            G[l][r] = cur

            # 结算最后一批:极差用原分数算,取所有可行区间里最小的一批代价
            hh[l][r] = min(cur[i] + a + b * (vals[y] - vals[x]) ** 2 for (x, y), i in zip(ps, ids))

            # 枚举最后一批的最左位置 s:[l,s-1] 是 s 左边的空隙,先独立取空
            dp[l][r] = min((0 if s == l else dp[l][s - 1]) + hh[s][r] for s in range(l, r + 1))

    return dp[0][n - 1]


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


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

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-08 00:39
// update_at: 2026-10-08 00:39
//
// 一本通 1766《成绩单》(= 洛谷 P5336 [THUSC2016] 成绩单)—— 区间 DP
//
// 【模型】一批成绩单不要求是原序列上的连续区间:中间的元素先被取走后,其左右两侧
// 在剩下的那一叠里就相邻了,可以并进同一批。因此只按「原序列连续区间划分」做线性 DP
// 是错的(题面样例会得到 21,正确答案是 15)。
//
// 【合法性刻画(只看位置,不看分数)】给每张成绩单赋一个批次时间 t(同批相同,
// 不同批不同)。设某批 B 的元素在原序列中最左 / 最右位置为 L、R,则 B 在被取走的
// 那一刻合法 <=> 所有满足 L < p < R 且 p 不属于 B 的位置 p 都已经先被取走。
//
// 【递归结构】对区间 [l,r],设 S 为其中最后被取走的那批(S 非空)。S 取走时 [l,r] 内
// 其余元素已全部取走,所以 S 必然合法;反过来,任何 S 也都能充当最后一批。并且 S 在
// [l,r] 内相邻两个位置之间的「空隙」(极大连续段)是互相独立的子问题 —— 若某个批次的
// 元素跨过 S 的某个元素,就与该批次的合法性矛盾。于是
//     dp[l][r] = min over 最后一批 S 的 ( a + b*(maxS-minS)^2 + Σ_空隙 dp[空隙] )
//
// 【状态】把分数离散化成 1..V 的排名(V <= n <= 50):
//   dp[l][r]        : 把区间 [l,r] 当成独立一叠全部发完的最小代价(空区间为 0)
//   g[l][r][x][y]   : 把 [l,r] 中「不属于最后一批」的元素全部消掉的最小代价;要求
//                     最后一批含位置 l,且其中所有分数的排名落在 [x,y] 内。
//                     不含最后一批自身的代价 a + b*(val[y]-val[x])^2
//   hh[s][r]        : [s,r] 中 s 作为最后一批最左元素时的最优总代价(含最后一批代价)
//                     = min_{x<=rank[s]<=y} ( g[s][r][x][y] + a + b*(val[y]-val[x])^2 )
//
// 【转移】按区间长度递增:
//   g[l][r][x][y] = min_{k=l}^{r-1} ( g[l][k][x][y] + min( dp[k+1][r],
//                                    g[k+1][r][x][y] 若 rank[k+1] 落在 [x,y] ) )
//       ([l,k] 留下含 l 的一批,[k+1,r] 要么整段先取空、要么也留下含 k+1 的一批并入)
//   基态 g[l][l][x][y] = 0(当且仅当 x <= rank[l] <= y,否则 INF)
//   dp[l][r] = min_{s=l}^{r} ( dp[l][s-1] + hh[s][r] )   ([l,s-1] 是 s 左边的空隙)
//   答案 dp[1][n]
//
// 【复杂度】时间 O(n^3 * V^2 / 4),n=V=50 实测 < 0.5s(限时 3000 ms);
//           空间 g[55][55][51][51] ≈ 31 MB(限时 256 MB)。
// 【取值上界】k <= n <= 50,每批代价 <= a + b*999^2,总和 < 5.0e8,int 足够;
//           INF = 1e9,两两相加不溢出 int。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 55;  // n <= 50
const int MAXV = 51;  // 不同分数个数 <= n <= 50
const int INF = 1000000000;  // 1e9:合法答案 < 5e8,INF + 合法值也不会溢出 int

int n;            // 成绩单数量
int a, b;         // 评估参数
int w[MAXN];      // w[i] : 第 i 张成绩单的原始分数(1 起)
int rankv[MAXN];  // rankv[i] : 第 i 张成绩单分数压缩后的排名(0 起)
int val[MAXV];    // val[x] : 排名 x 对应的原始分数
int V;            // 不同分数的个数

int dp[MAXN][MAXN];  // dp[l][r] : 把区间 [l,r] 当成独立一叠全部发完的最小代价
int hh[MAXN][MAXN];  // hh[s][r] : s 作为最后一批最左元素时 [s,r] 的最优总代价
// g[l][r][x][y] : 消掉 [l,r] 中不属于最后一批的元素,最后一批含 l 且排名落在 [x,y]
static int g[MAXN][MAXN][MAXV][MAXV];

int main() {
    if (scanf("%d %d %d", &n, &a, &b) != 3) return 0;
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);

    // ---------- 离散化:分数 -> 排名 ----------
    vector<int> vs(w + 1, w + n + 1);
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    V = (int)vs.size();
    for (int x = 0; x < V; ++x) val[x] = vs[x];
    for (int i = 1; i <= n; ++i)
        rankv[i] = (int)(lower_bound(vs.begin(), vs.end(), w[i]) - vs.begin());

    // ---------- 初始化 ----------
    // 非法状态一律 INF:排名不在 [x,y] 内的位置不可能属于最后一批
    for (int l = 1; l <= n; ++l)
        for (int r = l; r <= n; ++r)
            for (int x = 0; x <= rankv[l]; ++x)
                for (int y = rankv[l]; y < V; ++y)
                    g[l][r][x][y] = INF;
    for (int i = 1; i <= n + 1; ++i) dp[i][i - 1] = 0;  // 空区间

    for (int l = 1; l <= n; ++l) {  // 长度 1 的基态:只留下 l 本身,无需先消任何元素
        for (int x = 0; x <= rankv[l]; ++x)
            for (int y = rankv[l]; y < V; ++y)
                g[l][l][x][y] = 0;
    }

    // ---------- 按区间长度递增递推 ----------
    for (int len = 1; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;

            // (1) g[l][r][x][y]:枚举分割点 k,左半留下含 l 的一批,右半二选一
            if (len > 1) {
                for (int x = 0; x <= rankv[l]; ++x) {
                    for (int y = rankv[l]; y < V; ++y) {
                        int best = INF;
                        for (int k = l; k < r; ++k) {
                            int left = g[l][k][x][y];
                            if (left >= INF) continue;
                            int right = dp[k + 1][r];  // 右半整段先取空
                            if (x <= rankv[k + 1] && rankv[k + 1] <= y) {
                                // 右半也留下含 k+1 的一批,并入同一个最后一批
                                int gv = g[k + 1][r][x][y];
                                if (gv < right) right = gv;
                            }
                            int cand = left + right;
                            if (cand < best) best = cand;
                        }
                        g[l][r][x][y] = best;
                    }
                }
            }

            // (2) hh[l][r]:把最后一批结算掉(枚举它的排名上下界,取最小的极差代价)
            int hbest = INF;
            for (int x = 0; x <= rankv[l]; ++x) {
                for (int y = rankv[l]; y < V; ++y) {
                    int gv = g[l][r][x][y];
                    if (gv >= INF) continue;
                    int d = val[y] - val[x];
                    int cand = gv + a + b * d * d;
                    if (cand < hbest) hbest = cand;
                }
            }
            hh[l][r] = hbest;

            // (3) dp[l][r]:枚举最后一批的最左位置 s,[l,s-1] 是它左边的空隙
            int dbest = INF;
            for (int s = l; s <= r; ++s) {
                int cand = dp[l][s - 1] + hh[s][r];
                if (cand < dbest) dbest = cand;
            }
            dp[l][r] = dbest;
        }
    }

    printf("%d\n", dp[1][n]);
    return 0;
}

复杂度

  • 时间:状态 O(n2)O(n^2) 个 dpdp、O(n2V2)O(n^2V^2) 个 gg,gg 的转移枚举分割点 O(n)O(n), 总计 O(n3V2)O(n^3V^2)(n=V=50n=V=50 时约 10710^7 次内层迭代)。实测 C++ 最慢的点 problem7(n=50n=50、V=50V=50、单调递增)用时 0.0170.017 s,内存 15.415.4 MB, 远低于 30003000 ms / 256256 MB。
  • 空间:g[55][55][51][51]g[55][55][51][51] 约 3131 MB(C++);Python 侧每个区间一张 V2V^2 的扁平表, 约 2525 MB 指针量级,实测峰值低于 256256 MB。
  • 代价上界:批数 k≤n≤50k \le n \le 50,每批代价 ≤a+b⋅9992\le a + b\cdot 999^2,总和 <5.0×108< 5.0\times 10^8, int 足够;实现里取 INF=109INF = 10^9,两个合法值相加也不会溢出。
  • Python 与 C++ 的关系:main.py 是同一算法(不是降级版本),只是把"最后一批的排名区间" [x,y][x,y] 限制在必然夹住 ranklrank_l 的组合上,从而少算大量恒为 ∞\infty 的状态。实测最慢的 problem10 用时 0.740.74 s,同样在 30003000 ms 内,本题不存在 Python 特有的 TLE 风险。

总结

  • "当前这一叠"是本题的陷阱:一批不要求是原序列上的连续区间,中间元素被取走后左右会拼接。 凡是按"原序列连续区间划分"做的 DP 都会在样例上得到 2121。
  • 合法性的判定只看位置:L<p<RL<p<R 且 p∉Bp \notin B 的位置 pp 必须更早取走。这条刻画把"取走顺序" 这个看起来像排列的问题,压成了区间 DP 能处理的结构。
  • 抓住"最后一批"当骨架:它以自己为界把区间切成互不相干的空隙,每个空隙独立成子问题; 这也是"区间里还剩一部分元素留给未来"这类问题的通用切法。
  • 状态只记必要信息:留下的元素未来只以"极值"的形式进入代价,所以 gg 只需记排名区间 [x,y][x,y], 不必记位置;再配合分数离散化(V≤nV \le n)就把 O(n5)O(n^5) 的常数压了下来。
  • 枚举去重:gg 强制"最后一批含最左位置 ll",把"ll 属于更小空隙"的情形交给 dpdp 的枚举, 避免了同一个方案被反复计数。
  • 本题素材源里带有数据生成脚本(data.py),说明 data/ 是本地自造的(按一本通题面 a≤100a \le 100、b≤10b \le 10、wi≤1000w_i \le 1000 造点),题面则是洛谷 P5336 [THUSC2016] 成绩单的重建版; 本解已用"每次取当前一叠连续段"的暴力搜索在 n≤9n \le 9 的随机数据上与 dpdp 对拍通过。