把最后被取走的一批当作区间骨架,其余元素被它切成互相独立的空隙;用 g[l][r][x][y] 记「留下含 l 的一批、其分数排名夹在 [x,y] 内」的代价,区间 DP 即可。
OJ: roj
题目 ID: 1766
难度:提高+/省选-
标签:动态规划区间DPpython
创建: 2026-10-08 00:39
更新: 2026-10-08 00:39
形式化题目
要求最小化代价。数据范围:
注意"抽取连续的一段"限定的是当前那一叠里的连续段,而不是原序列上的连续区间:
中间的元素被先抽走后,它左右两侧在剩下的那一叠里就相邻了,于是可以并进同一批。
这一点是本题的分水岭 —— 若误以为"每一批都是原序列上的连续区间",问题退化成
样例
| 批次 | 取走的元素(按原序列位置) | 分数 | 极差 | 代价 |
|---|---|---|---|---|
| 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 批在原序列上占位置
正解
思路
先给"一批合法"下一个只看位置的刻画。 给每张成绩单赋一个批次时间
必要性:若这样的
判定条件里只出现位置,分数只通过
朴素做法与瓶颈。 枚举每一轮取哪一段,状态随轮数指数爆炸(
关键观察:以"最后一批"为骨架。 对区间
中的每一批,其元素必整体落在 在 内相邻两个位置之间的 空隙(极大连续段)里。
否则某批
状态。 空隙的划分只取决于"留下哪些位置",而留下的那批元素未来的代价只取决于它的
分数极值。把分数离散化(
:把区间 当成独立的一叠全部发完的最小代价(空区间为 ); :把 中"不属于最后一批"的元素全部消掉的最小代价,要求最后一批含位置 (用它去重: 不属于最后一批时, 必然落在某个更小的空隙里,那属于下一种枚举), 且其中所有分数的排名都落在 内;这个状态不含最后一批自身的代价; : 中 作为最后一批最左元素时的最优总代价(已经结算过最后一批)。
转移。 按区间长度从小到大递推。固定
第一步,枚举分割点
即右半要么整段先取空(代价
第二步,结算最后一批。枚举它的排名上下界(必然夹住
这里用的是
第三步,
答案是
为什么这样不重不漏。 设最优方案在
代码
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++ 版(同一算法):
// 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;
}复杂度
- 时间:状态
个 、 个 , 的转移枚举分割点 , 总计 ( 时约 次内层迭代)。实测 C++ 最慢的点 problem7(、 、单调递增)用时 s,内存 MB, 远低于 ms / MB。 - 空间:
约 MB(C++);Python 侧每个区间一张 的扁平表, 约 MB 指针量级,实测峰值低于 MB。 - 代价上界:批数
,每批代价 ,总和 , int足够;实现里取,两个合法值相加也不会溢出。 - Python 与 C++ 的关系:
main.py是同一算法(不是降级版本),只是把"最后一批的排名区间"限制在必然夹住 的组合上,从而少算大量恒为 的状态。实测最慢的 problem10用时s,同样在 ms 内,本题不存在 Python 特有的 TLE 风险。
总结
- "当前这一叠"是本题的陷阱:一批不要求是原序列上的连续区间,中间元素被取走后左右会拼接。
凡是按"原序列连续区间划分"做的 DP 都会在样例上得到
。 - 合法性的判定只看位置:
且 的位置 必须更早取走。这条刻画把"取走顺序" 这个看起来像排列的问题,压成了区间 DP 能处理的结构。 - 抓住"最后一批"当骨架:它以自己为界把区间切成互不相干的空隙,每个空隙独立成子问题; 这也是"区间里还剩一部分元素留给未来"这类问题的通用切法。
- 状态只记必要信息:留下的元素未来只以"极值"的形式进入代价,所以
只需记排名区间 , 不必记位置;再配合分数离散化( )就把 的常数压了下来。 - 枚举去重:
强制"最后一批含最左位置 ",把" 属于更小空隙"的情形交给 的枚举, 避免了同一个方案被反复计数。 - 本题素材源里带有数据生成脚本(
data.py),说明data/是本地自造的(按一本通题面、 、 造点),题面则是洛谷 P5336 [THUSC2016] 成绩单的重建版; 本解已用"每次取当前一叠连续段"的暴力搜索在 的随机数据上与 对拍通过。