两种删除代价分别优化:代价①是二次型用斜率优化维护下凸壳,代价②的合法分割点构成随 i 单调右移的连续区间,用双指针加单调队列求区间最小值,总复杂度 O(n)。
OJ: roj
题目 ID: 1793
难度:提高+/省选-
标签:动态规划斜率优化单调队列双指针python
创建: 2026-10-08 03:33
更新: 2026-10-08 03:33
形式化题目
给定长度
其中
即删去每个前缀
因为
记
正解
思路
先看朴素 DP 的瓶颈。 直接按上面的转移式做,对每个
关键想法:两种删除方式的结构完全不同,把它们拆开、各自用最合适的数据结构求最小值。 即分别求出
其中
方法①:二次型代价 → 斜率优化。 展开转移式:
固定
则
由于
一个必须处理的坑:
可以取 ,此时 ,两个决策点的横坐标重合。 直接用 判凸性会除零;而且同横坐标的点只有 最小的那个有意义。 实现里一律用交叉相乘判斜率( 乘法升到 __int128防溢出), 并在入队前先对同横坐标去重。
方法②:条件本身有单调性 → 双指针 + 单调队列。 把转移式展开:
只要
固定右端点
于是:
- "最大频次
"要求窗口足够短 ⇒ 合法的 是一段后缀 ; - "最大频次
"要求窗口足够长 ⇒ 合法的 是一段前缀 。
两者相交,
而且
每一项都是"某个字符第固定次数出现的位置",随
于是问题变成:在左右端点都单调不减的滑动窗口
两种方法的合并。 每个
小规模手算样例。 样例为
| 方法①最优 |
方法②可用 |
方法②最优 |
||||
|---|---|---|---|---|---|---|
| 1 | 0 | a 出现 1 次) |
0 | 4 | ||
| 2 | 0 | 0 | 7 | |||
| 3 | 2 | bwa 互不相同) |
0 | 8 | ||
| 4 | 3 | 1 | 12 | |||
| 5 | 3 | 1 | 13 |
第 4 行是双指针必须小心的地方:abwad 里 a 出现 2 次,
代码
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 03:30
# update_at: 2026-10-08 03:30
import sys
from collections import deque
HULL_NEED = 2 # 下凸壳至少留几个点才能判断中间点冗余
type IndexQueue = deque[int] # 决策点下标队列:方法① 的凸壳与方法② 的滑动窗口各用一个
def delete_costs(n: int, a: int, b: int, c: int, d: int, lmin: int, rmax: int,
s: bytes, dif: list[int]) -> list[int]:
"""依次算出删去每个前缀 [1,i] 的最少用时:返回长度 n 的答案表 dp[1..n]。
方法①(代价 a*x^2+b)用斜率优化维护下凸壳;方法②(代价 c*x+d)的合法分割点构成
随 i 单调右移的连续区间,用双指针维护区间端点、单调队列取区间内最小值。
"""
pre = [0] * (n + 1) # pre[i] = 前缀 [1,i] 的删除难度之和
for i in range(1, n + 1):
pre[i] = pre[i - 1] + dif[i - 1] # dif >= 0,故 pre 单调不减
dp = [0] * (n + 1) # dp[i] = 删去前缀 [1,i] 的最少用时
occ: list[list[int]] = [[] for _ in range(26)] # occ[ch] = 字符 ch 出现位置的升序表
hull: IndexQueue = deque() # 下凸壳上的决策点下标
window: IndexQueue = deque() # 合法区间内 h(j) 递增的决策点下标
def yval(j: int) -> int:
"""方法① 凸壳上决策点 j 的纵坐标 dp[j] + a*pre[j]^2。"""
return dp[j] + a * pre[j] * pre[j]
def hvalue(j: int) -> int:
"""方法② 中与右端点无关的贡献 dp[j] - c*pre[j]。"""
return dp[j] - c * pre[j]
def hull_push(j: int) -> None:
"""把决策点 j 压入方法① 的下凸壳(横坐标重合时只留纵坐标更小者)。"""
xj = pre[j]
if hull and pre[hull[-1]] == xj: # dif 含 0 时横坐标会重合,凸壳不能带重复 x
if yval(hull[-1]) <= yval(j):
return
hull.pop()
while len(hull) >= HULL_NEED:
p, q = hull[-2], hull[-1]
# 下凸壳约定:slope(p,q) >= slope(q,j) 说明 q 在弦上方,应丢弃。
# 交叉相乘代替除法,避免 dif=0 时除零,也避免浮点误差。
q_redundant = (yval(q) - yval(p)) * (xj - pre[q]) >= (yval(j) - yval(q)) * (pre[q] - pre[p])
if not q_redundant:
break
hull.pop()
hull.append(j)
def hull_best(k: int) -> int:
"""在查询斜率 k = 2a*pre[i] 下取最优决策点;k 单调不减,队头只往前移。"""
while len(hull) >= HULL_NEED:
j0, j1 = hull[0], hull[1]
# 队头不如第二个点时就弹掉队头(k 递增,被弹掉的不会再变好)
front_worse = yval(j0) - k * pre[j0] >= yval(j1) - k * pre[j1]
if not front_worse:
break
hull.popleft()
return hull[0]
sL = sR = 0 # 方法② 的合法决策区间固定是 [sR, sL-1],两个端点都随 i 单调不减
pushed = -1 # window 中已经推入的最大下标
ans: list[int] = []
for i in range(1, n + 1):
ch = s[i - 1] - 97 # 当前字符
occ[ch].append(i)
cnt = len(occ[ch])
# 第 (cnt-lmin+1) 次出现的位置:左端点取它时窗口内 ch 恰有 lmin 个 => maxfreq >= lmin
if cnt >= lmin:
sL = max(sL, occ[ch][cnt - lmin])
# 第 (cnt-rmax) 次出现的位置:左端点越过它后 ch 就超过 rmax 个 => maxfreq <= rmax
if cnt > rmax:
sR = max(sR, occ[ch][cnt - rmax - 1])
while pushed < sL - 1: # 右端点单调不减,逐个把新决策点推进去
pushed += 1
hv = hvalue(pushed)
while window and hvalue(window[-1]) >= hv:
window.pop()
window.append(pushed)
while window and window[0] < sR: # 左端点单调不减,弹出过期决策点
window.popleft() # lmin > rmax 时区间为空,队列被清空
hull_push(i - 1)
j1 = hull_best(2 * a * pre[i]) # 方法①:凸壳上的最优分割点
best = dp[j1] + a * (pre[i] - pre[j1]) ** 2 + b
if window: # 方法②:区间非空才可用
j2 = window[0]
cand = dp[j2] - c * pre[j2] + c * pre[i] + d
if cand < best:
best = cand
dp[i] = best
ans.append(best)
return ans
def solve() -> None:
# 输入是严格的三行结构:第一行 7 个整数、第二行字符串、第三行 n 个整数,按行读最直接。
n, a, b, c, d, lmin, rmax = map(int, sys.stdin.buffer.readline().split())
s = sys.stdin.buffer.readline().strip() # 字符串行,取下标得 ASCII 码
dif = list(map(int, sys.stdin.buffer.read().split()))
print("\n".join(map(str, delete_costs(n, a, b, c, d, lmin, rmax, s, dif))))
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 03:30
* update_at: 2026-10-08 03:30
*/
// 一本通 1793《鏖战字符串》
// 题意:给出长度 n 的字符串与每个位置的删除难度 dif[i](0 <= dif[i] <= 50)。
// 要把前缀 [1,i] 切成若干连续子串,每个子串二选一删除:
// ① 代价 a*x^2 + b (x = 子串内 dif 之和)
// ② 代价 c*x + d,当且仅当子串中出现次数最多的字符出现次数 ∈ [l, r]
// 求删去每个前缀 [1,i] 的最少用时,输出 n 行。
//
// 算法(O(n)):
// pre[i] = sum_{k<=i} dif[k](因 dif >= 0,pre 单调不减),dp[0] = 0。
// dp[i] = min_{0<=j<i} { dp[j] + cost(j+1, i) },
// cost(j+1,i) = min( a*X^2 + b , [maxfreq(j+1,i) ∈ [l,r]] * (c*X + d) ),X = pre[i]-pre[j]。
//
// (A) 方法① —— 斜率优化(下凸壳):
// dp[j] + a*(pre[i]-pre[j])^2 + b = a*pre[i]^2 + b + ( dp[j] + a*pre[j]^2 ) - 2a*pre[i]*pre[j]
// 点 (X_j, Y_j) = (pre[j], dp[j] + a*pre[j]^2),查询斜率 K_i = 2a*pre[i]。
// X_j 与 K_i 都随 i 单调不减 => 维护下凸壳 + 单调队列,均摊 O(1) 查一次。
//
// (B) 方法② —— 频次窗口 + 滑动窗口最小值:
// 固定 i,maxfreq(j+1, i) 随 j 增大单调不增(窗口变短)。
// 于是「maxfreq >= l」的 j 构成前缀 j <= sL-1,「maxfreq <= r」的 j 构成后缀 j >= sR,
// 合法集合是连续区间 [sR, sL-1](l > r 时为空,方法② 自动失效,退化为纯 (A))。
// sL = max_c ( 字符 c 第 (cnt_c-l+1) 次出现的位置 ),sR = max_c ( 第 (cnt_c-r) 次出现的位置,不足取 0 );
// 两者都随 i 单调不减,故 [sR, sL-1] 是双指针维护的滑动窗口。
// 区间内最小化 dp[j] - c*pre[j](与 i 无关)用单调队列,均摊 O(1)。
//
// 复杂度 O(n) 时间、O(n) 空间。中间量最大约 233 * (50*1e5)^2 ≈ 5.8e15,long long 安全。
// dif[i] = 0 时会出现 pre[j] == pre[j-1](横坐标重合),凸壳入队时单独去重,不能直接除斜率。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int MAXN = 100005;
ll n; // 字符串长度
ll A, B, C, D; // 题面的 a, b, c, d
ll LNEED, RNEED; // 题面的 l, r
char str_[MAXN]; // 字符串,1-based
ll dif[MAXN]; // dif[i]:第 i 个字符的删除难度
ll pre[MAXN]; // pre[i]:前缀 [1,i] 的删除难度之和
ll dp[MAXN]; // dp[i]:删去前缀 [1,i] 的最少用时
int occ[26][MAXN]; // occ[ch][k]:字符 ch 第 k 次出现的位置(1-based,k 从 1 开始)
int cnt[26]; // cnt[ch]:字符 ch 到目前为止的出现次数
// ---- 方法①:斜率优化(下凸壳)用的单调队列,存决策点下标 j ----
int hull[MAXN];
int hh, ht; // 凸壳区间为 [hh, ht)
// 凸壳上决策点 j 的纵坐标 Y_j = dp[j] + a*pre[j]^2
ll yval(int j) {
return dp[j] + A * pre[j] * pre[j];
}
// 下凸壳维护:slope(p,q) >= slope(q,r) 时 q 冗余(交叉相乘,避免除法与浮点误差)
bool hull_bad(int p, int q, int r) {
lll lhs = (lll)(yval(q) - yval(p)) * (pre[r] - pre[q]);
lll rhs = (lll)(yval(r) - yval(q)) * (pre[q] - pre[p]);
return lhs >= rhs;
}
// 把决策点 j 插入下凸壳
void hull_add(int j) {
if (ht > hh && pre[hull[ht - 1]] == pre[j]) { // 横坐标重合(dif 出现 0),只留 Y 更小者
if (yval(hull[ht - 1]) <= yval(j)) return;
ht--;
}
while (ht - hh >= 2 && hull_bad(hull[ht - 2], hull[ht - 1], j)) ht--;
hull[ht++] = j;
}
// 查询斜率 K 下的最优决策点;K 随 i 单调不减,队头只往后走,均摊 O(1)
int hull_best(ll K) {
while (ht - hh >= 2) {
int j0 = hull[hh], j1 = hull[hh + 1];
if (yval(j0) - K * pre[j0] >= yval(j1) - K * pre[j1]) hh++;
else break;
}
return hull[hh];
}
// ---- 方法②:滑动窗口最小值的单调队列,存下标 j,按 dp[j]-c*pre[j] 递增 ----
ll win[MAXN];
int wh, wt;
int main() {
if (scanf("%lld %lld %lld %lld %lld %lld %lld", &n, &A, &B, &C, &D, &LNEED, &RNEED) != 7) return 0;
scanf("%s", str_ + 1);
for (int i = 1; i <= n; i++) {
scanf("%lld", &dif[i]);
pre[i] = pre[i - 1] + dif[i]; // dif >= 0,pre 单调不减
}
dp[0] = 0;
ll sL = 0, sR = 0; // 合法决策区间为 [sR, sL-1]
ll pushed = -1; // win 中已推入的最大下标
for (int i = 1; i <= n; i++) {
int ch = str_[i] - 'a';
cnt[ch]++;
occ[ch][cnt[ch]] = i;
// 更新 sL:字符 ch 第 (cnt-l+1) 次出现的位置,说明以它为左端点的窗口装得下 >= l 个 ch
ll k1 = cnt[ch] - LNEED + 1;
if (k1 >= 1 && occ[ch][k1] > sL) sL = occ[ch][k1];
// 更新 sR:字符 ch 第 (cnt-r) 次出现的位置,左端点越过它后 ch 的出现次数必 <= r
ll k2 = cnt[ch] - RNEED;
if (k2 >= 1 && occ[ch][k2] > sR) sR = occ[ch][k2];
// 右端点 sL-1 单调不减,逐个把新决策点推入单调队列
while (pushed < sL - 1) {
pushed++;
ll hv = dp[pushed] - C * pre[pushed];
while (wt > wh && dp[win[wt - 1]] - C * pre[win[wt - 1]] >= hv) wt--;
win[wt++] = pushed;
}
// 左端点 sR 单调不减,弹出过期决策点(sR > sL-1 时队列会被清空,方法② 失效)
while (wt > wh && win[wh] < sR) wh++;
hull_add(i - 1); // 决策点 j = i-1 此刻的 dp 已确定,先入凸壳再查询
int j1 = hull_best(2 * A * pre[i]); // 方法①的最优分割点
ll best = dp[j1] + A * (pre[i] - pre[j1]) * (pre[i] - pre[j1]) + B;
if (wt > wh) { // 方法②可用:区间 [sR, sL-1] 非空
ll j2 = win[wh];
ll cand = dp[j2] - C * pre[j2] + C * pre[i] + D;
if (cand < best) best = cand;
}
dp[i] = best;
printf("%lld\n", dp[i]);
}
return 0;
}复杂度
- 时间:前缀和
;凸壳中每个决策点最多入队出队各一次, ; 双指针中 、 各单调右移最多 次, ;方法②的单调队列同样 。 每次更新字符出现位置需要按字符维护位置列表,均摊 。总计 , 常数很小, 时实测在毫秒级(限时 1000 ms)。 - 空间:
、 、凸壳、单调队列、以及每个字符的出现位置(合计 个),都是 。 C++ 侧约 个 64 位整数加上位置表,实测峰值内存远低于 128 MB。 - 数值范围:
, 最大中间量 , 超过 32 位整数,必须用 64 位;凸壳判斜率时的交叉相乘再升一档到 __int128。
总结
- 按代价的结构拆转移:同一个 DP 的两种转移如果形状不同(一个二次、一个线性), 不要硬塞进一个数据结构,拆开后各自可以用最简单的工具解决。
- 斜率优化的两个单调性:入队点的横坐标单调、查询斜率单调,二者同时成立才能用单调队列维护凸壳;
本题由
单调不减保证。横坐标重合( )时必须去重并用交叉相乘判凸性。 - "合法决策点构成连续区间,且端点单调"是滑动窗口的标志:方法②的条件只跟子串内的频次有关,
窗口越长最大频次越大,于是合法
天然是区间,且随着 右移整体右移。 - 不可用状态要能自然退化:
时方法② 恒不可用,双指针会让左端点越过右端点、 单调队列被清空,此时必须显式判断"区间非空"再取值。 - 本题数据说明:素材源自带了数据生成脚本(
data.py),说明本题的测试数据是自行构造的 (按题面分 10 个难度层次:边界、样例、小/中/大规模、全同字符、{a,b}字符集、l > r等), 原题(一本通·高手训练)的官方数据不可得;因此本文的结论只在"题面 + 这套数据"上经过验证, 与官方原题数据可能有差异。素材源的std.cpp与本解思路一致(同为凸壳 + 频次窗口,但写法不同), 编译后在 10 个真实点与数百组随机小数据上与本文两份实现逐字节一致,可以互相印证; 但两者都不等于官方标程。