「做题记录」动态规划选做 — Part 1

· · 算法·理论

Part 1 主要是线性结构上的最优化 DP 问题,会涉及一些 DP 优化。Part 2。

HDU5501 The Highest Mark

给出 n 个任务 (a_i,b_i,c_i) 和一个时刻上限 m。你可以在任意时刻开始完成一个任务,完成任务需要花费 c_i 的时间。若在 t 时刻完成且 t \le m,则获得 a_i-t\times b_i 的得分。

不允许同时进行多个任务,可以以任意顺序完成任务。最大化得分并输出。

多测,T \le 10,n \le 1000,m \le 3000,1 秒,128 MB。

:::::success[题解] 邻项交换确定 DP 顺序模板题。

如果我们可以确定一个做题顺序,就可以顺着做 01 背包。设 f_j 为前 j 时刻内的最大得分,加入任务 i 则做转移

f_j \gets f_{j-c_i}+a_i-j \times b_i

考虑做 exchange argument 来确定 DP 顺序。设当前用时为 t,两个任务分别为 i,j:

作差得

X-Y=c_jb_i-c_ib_j

所以定义 \prec 为 c_ib_j<c_jb_i。另外发现 c_ib_j<c_jb_i \iff \dfrac{c_i}{b_i} < \dfrac{c_j}{b_j},所以是 \prec 是一个严格全序。

复杂度 O(Tnm)。

:::::info[代码]

const int N = 3005;
int n, m;
struct node {
    int a, b, c;
} a[N];
i64 f[N];

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b >> a[i].c;
    sort(a + 1, a + n + 1, [](const node& x, const node& y) {
        return 1LL * x.c * y.b < 1LL * y.c * x.b;
    });
    fill(f, f + m + 1, 0);
    for (int i = 1; i <= n; i++) 
        for (int j = m; j >= a[i].c; j--) 
            f[j] = max(f[j], f[j - a[i].c] + a[i].a - 1LL * j * a[i].b); 
    cout << *max_element(f, f + m + 1) << '\n';
} 

:::::

P10971 Cookies

现有 m 个元素要分给 n 个人,第 i 个人有属性值 a_i,如果有 x 个人拿到的元素比第 i 个人多,则产生 a_i\times x 的代价。每个人至少要分到一个元素,且所有 m 个元素要全部分完,求最小代价,并构造一组方案。

:::::success[题解] 观察性质起手:对于 a_i 较大的人,分配到的元素一定只多不少,调整法容易证明。

按照 a_i 降序排序确定 DP 顺序。然后设 f_{i,j} 为考虑前 i 个人,分配了 j 个元素的最小代价。

讨论给第 i 个人分配的元素数目,则我们需要正确计算 x 才能转移,但事实上从上述状态中无法计算出 x。由于本题的转移结构比较特殊,我们可以利用等效替代的 trick:

对 a_i 做一个前缀和后复杂度 O(n^2m)。构造方案就记录决策点然后倒推回去,根据转移的实际意义还原即可。

:::::info[代码]

const int N = 5005;
using node = pair<int, int>;
int n, m, f[31][N], pre[N], tmp[N], ans[N];
node a[N], opt[31][N];

void dfs(int i, int j) {
    if (i == 0 && j == 0) return;
    auto [ni, nj] = opt[i][j];
    dfs(ni, nj);
    if (i == ni) {
        for (int k = 1; k <= ni; k++) tmp[k]++;
    } else {
        for (int k = ni + 1; k <= n; k++) tmp[k] = 1;
    } 
}

void _main() {
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++) cin >> x, a[i] = {x, i};
    sort(a + 1, a + n + 1, greater<node>());
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i].first;
    memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= m; j++) {
            if (f[i][j - i] < f[i][j]) {
                f[i][j] = f[i][j - i];
                opt[i][j] = {i, j - i};
            }
            for (int k = 0; k < i; k++) {
                int v = f[k][j - i + k] + k * (pre[i] - pre[k]);
                if (v < f[i][j]) f[i][j] = v, opt[i][j] = {k, j - i + k};
            }
        }
    }
    cout << f[n][m] << '\n';
    dfs(n, m);
    for (int i = 1; i <= n; i++) ans[a[i].second] = tmp[i];
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

:::::

P8903 [USACO22DEC] Bribing Friends G

现有 n 个元素 (p_i,c_i,x_i)。你初始持有 a 元钱和 b 张优惠券。对于第 i 个元素,你可以支付 c_i 元获得 p_i 的得分。同时,如果你支付 x_i 张优惠劵,你还可以获得 1 元的折扣,折扣的上限为 c_i。最大化得分并输出。

:::::success[题解] 容易设计一个 DP:记 f_{i,j,k} 为考虑到第 i 个元素,当前持有 j 元钱,k 张优惠券,枚举对第 i 个元素支付的优惠券可以转移。视 n,V 同阶复杂度 O(n^4),无法通过。

我们需要发现性质,然后用贪心优化 DP。

考虑如下情景:我们已经确定了最优解中选择哪些元素。这种情况下有一个贪心:我们按 x_i 升序排序,并且顺次使用优惠券。

对于前面的元素,我们一定是尽量使用优惠券直到买满。那么整个场面上至多有一个元素没有被买满,是使用钱 + 优惠券混用得到的。

拓展到一般情况,将元素按 x_i 升序排序后,最优解一定形如:

我们可以对前缀做一个 (p_i,x_i) 的背包,对后缀做一个 (p_i,c_i) 的背包。在计算答案时,只需枚举中点,再枚举中点元素使用的优惠券数目,即用 (\max,+) 卷积合并前后缀背包。

复杂度 O(n^2),有一些 corner case。

:::::info[代码]

const int N = 2005;
int n, a, b, f[N][N], g[N][N];
struct node {
    int p, c, x;
} c[N];

void _main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> c[i].p >> c[i].c >> c[i].x;
    sort(c + 1, c + n + 1, [](const node& a, const node& b) -> bool {
        return a.x < b.x;
    });
    for (int i = 1; i <= n; i++) {
        int w = c[i].c * c[i].x;
        for (int j = 0; j <= b; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= w) f[i][j] = max(f[i][j], f[i - 1][j - w] + c[i].p);
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= a; j++) {
            g[i][j] = g[i + 1][j];
            if (j >= c[i].c) g[i][j] = max(g[i][j], g[i + 1][j - c[i].c] + c[i].p);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= c[i].c; j++) {
            if (j * c[i].x > b || c[i].c - j > a) continue;
            res = max(res, f[i - 1][b - j * c[i].x] + g[i + 1][a - c[i].c + j] + c[i].p);
        }
    } cout << res;
} 

:::::

【无题解】P11233 [CSP-S 2024] 染色

【无题解】P9119 [春季测试 2023] 圣诞树

P8162 [JOI 2022 Final] 让我们赢得选举 / Let's Win the Election

给出 n 个任务 (a_i,b_i),b_i 可能为 +\infty。你初始持有 d=1,对于第 i 个任务,可以选择一个实数 x,若 dx \ge a_i 则获得 1 的得分,若 dx \ge b_i 则令 d \gets d+1。此操作支付 x 的代价。

每个任务只能获得一次得分,求获得 k 得分的最小代价。

:::::success[题解]

对第 i 个任务,不难发现最优解满足 x_i \in \{0,a_i,b_i\}。

如果我们钦定了 x_i,则最优顺序一定是先执行 x_i=b_i 的任务使得 d 较大,再执行 x_i=a_i 的任务。并且根据排序不等式,执行 x_i=b_i 的任务时按 b_i 升序排序即最优顺序。

如果我们确定了 x_i=b_i 的任务集合,则 a_i 直接排序贪心选取即可。这启发我们枚举 m 并钦定恰好选 m 个 x_i=b_i。

根据上述分析,按 b_i 升序排序可以形成最优子结构,因此考虑 DP。记 f_{i,j,k} 为考虑前 i 个任务,选择 j 个 x_i=b_i 的任务,k 个 x_i=a_i 的任务的最小代价,转移时考虑当前任务是哪种情况即可,复杂度 O(n^4)。

进一步,我们可以使用调整法说明:在这段特定前缀不存在 x_i=0 的任务。找到最后一个 x_j=b_j 的任务 j,并令 x_i=b_i,x_j=0 更优。

于是我们有 j+k=i,那么可以省略一维,总复杂度即 O(n^3)。

:::::

:::::info[代码]

const int N = 505;
const double inf = 1e18;
int n, k;
struct node {
    double a, b;
} a[N];
double v[N], f[N][N];

double work(int m) {
    for (int i = 1; i <= n; i++) v[i] = a[i].a;
    for (int i = 1; i <= n; i++) fill(f[i], f[i] + i + 1, inf);
    f[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= min(m, i); j++) {
            chkmin(f[i + 1][j], f[i][j] + a[i + 1].a / (m + 1));
            chkmin(f[i + 1][j + 1], f[i][j] + a[i + 1].b / (j + 1));
        }
    }
    double res = inf;
    for (int i = k; i <= n; i++) chkmin(res, f[i][m]);
    for (int i = k - 1; i >= m; i--) {
        sort(v + i + 1, v + n + 1);
        chkmin(res, f[i][m] + accumulate(v + i + 1, v + k + 1, 0.0) / (m + 1));
    } return res;
} 

void _main() {
    cin >> n >> k;
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;
        a[i].a = x, a[i].b = (y == -1 ? inf : y);
    }
    sort(a + 1, a + n + 1, [](const node& a, const node& b) -> bool {
        return a.b < b.b;
    });
    double res = inf;
    for (int i = 0; i <= k; i++) res = min(res, work(i));
    cout << fixed << setprecision(12) << res;
} 

:::::

P11630 [WC2025] 士兵

给出 n 个二元组 (a_i,b_i),一次操作支付 m 的代价,将一个区间上的所有 a_i 减 1。所有操作结束后,你的得分为 \sum\limits_{i=1}^n b_i[a_i \le 0]。

最大化得分减去代价的值。

多测,\sum n \le 5 \times 10^5,1 \le a_i,m \le 10^9,-10^9 \le b_i \le 10^9。2 秒,1024 MB。

:::::success[题解] 我们任意赋一组非负整数 x_i 表示第 i 个位置被操作的次数,总能找到一种方案。这时的最小操作次数为 \sum \limits_{i=1}^n \max(0,x_i-x_{i-1})。

写出答案式子为

\sum _{i=1}^n b_i[x_i \ge a_i]-m\sum _{i=1}^n \max(0,x_i-x_{i-1})\\ =\sum_{i=1}^n \left(b_i[x_i \ge a_i]-m \times \max(0,x_i-x_{i-1})\right)

容易把贡献拆到每个位置 i 上。据此设计一个 DP,令 f_{i,j} 表示考虑前 i 个元素,满足 x_i=j 时前缀的最大得分,转移是平凡的,做到 O(nV)。这个东西很难优化,所以需要先把状态压下来。

进一步,考察操作的性质。注意到令 x_i \gets x_{i-1} 总能避免 m 的代价。考虑 x_i 序列的形态,则其仅在特定位置产生突变。具体地:

此时我们并不需要记录 O(V) 种决策,直接将状态改为:f_i 表示考虑前 i 个元素,且 i 处产生突变的最大得分。我们记 c_i=a_i-[b_i<0],则 f_i 是原本的 f_{i,c_i}。

枚举上一个突变点 j,此时 \forall k \in [j,i), x_i \gets c_j。二者之间产生 m \times \max(0,c_i-c_j) 的代价。同时我们需要枚举 k \in (j,i) 判断这些点是否被顺带消除,得到式子:

f_i=\max(0,b_i)+\max_{j=0}^{i-1} \left(f_j - m \times \max(0,c_i-c_j) +\sum_{k=j+1}^{i-1} b_k [c_i \ge a_k] \right)

倒序枚举 j 即可动态维护后面那个求和式,做到 O(n^2),获得 35pts。

int n, m, a[N], b[N], c[N], f[N];
void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], c[i] = a[i] - (b[i] < 0);
    fill(f + 1, f + n + 1, -1e18);
    for (int i = 1; i <= n; i++) {
        int v = 0;
        for (int j = i - 1; j >= 0; j--) {
            f[i] = max(f[i], max(0LL, b[i]) + f[j] - m * max(0LL, c[i] - c[j]) + v);
            if (c[i] >= a[j]) v += b[j];
        }
    }
    cout << *max_element(f, f + n + 1) << '\n';
}

令 h(l,r)=\sum\limits_{k=l+1}^{r-1} b_k [c_r \ge a_k]。注意到转移式中有 \max(0,c_i-c_j) 这个东西,考虑分类讨论:

离散化以后,将两棵线段树建在 c_i 上,分别维护两种情况,需要支持区间加、区间 chkmax,复杂度 O(n \log n)。

:::::info[代码]

int n, m, len, a[N], b[N], c[N], d[N << 1];
int idx(int x) {return lower_bound(d + 1, d + len + 1, x) - d;}

struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    constexpr static int inf = 1e18;
    int val[N << 3], add[N << 3], cmax[N << 3];
    void pushup(int rt) {val[rt] = max(val[ls], val[rs]);}
    void apply(int rt, int ad, int cm) {
        val[rt] = max(val[rt] + ad, cm), add[rt] += ad;
        cmax[rt] = max(cmax[rt] + ad, cm);
    }
    void pushdown(int rt) {
        apply(ls, add[rt], cmax[rt]), apply(rs, add[rt], cmax[rt]), add[rt] = 0, cmax[rt] = -inf;
    }
    void build(int l = 0, int r = len, int rt = 1) {
        add[rt] = 0, cmax[rt] = -inf, val[rt] = -inf;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs);
    }
    void uadd(int tl, int tr, int c, int l = 0, int r = len, int rt = 1) {
        if (tl <= l && r <= tr) return apply(rt, c, -inf), void();
        int mid = (l + r) >> 1;
        pushdown(rt);
        if (tl <= mid) uadd(tl, tr, c, l, mid, ls);
        if (tr > mid) uadd(tl, tr, c, mid + 1, r, rs);
        pushup(rt);
    }
    void umax(int tl, int tr, int c, int l = 0, int r = len, int rt = 1) {
        if (tl <= l && r <= tr) return apply(rt, 0, c), void();
        int mid = (l + r) >> 1;
        pushdown(rt);
        if (tl <= mid) umax(tl, tr, c, l, mid, ls);
        if (tr > mid) umax(tl, tr, c, mid + 1, r, rs);
        pushup(rt);
    }
    int ask(int x, int l = 0, int r = len, int rt = 1) {
        if (l == r) return val[rt];
        int mid = (l + r) >> 1;
        pushdown(rt);
        return x <= mid ? ask(x, l, mid, ls) : ask(x, mid + 1, r, rs);
    }
} T1, T2;

void _main() {
    cin >> n >> m, len = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i], c[i] = a[i] - (b[i] < 0);
        d[++len] = a[i], d[++len] = a[i] - 1;
    }
    sort(d + 1, d + len + 1), len = unique(d + 1, d + len + 1) - d - 1;
    T1.build(), T2.build();
    T1.umax(0, 0, 0), T2.umax(0, len, 0);
    for (int i = 1; i <= n; i++) {
        int v1 = T1.ask(idx(c[i])), v2 = T2.ask(idx(c[i])) - m * c[i];
        int v = max(v1, v2) + max(0LL, b[i]);
        T1.uadd(idx(a[i]), len, b[i]), T2.uadd(idx(a[i]), len, b[i]);
        T1.umax(0, idx(c[i]), v), T2.umax(idx(c[i]), len, v + m * c[i]);
    } cout << T1.val[1] << '\n';
}

:::::

ABC225F String Cards

给出 n 个字符串 S_i。你需要选出 k 个字符串,并按某个顺序拼接,最小化这个串的字典序并输出。

:::::success[题解] 注意到 P1012 即本题 k=n 的特殊情形。考虑套用这个题的方法:定义 A \prec B \iff AB<BA,按照 \prec 将字符串集合排序。可证 \prec 是严格全序。

直接选择一段长为 k 的前缀是错的。原因是长度不固定,如 [\tt{ba},\tt{a},\tt{ba}],显然 \tt{bab} 优于 \tt{baba}。

考虑 DP。记 f_{i,j} 为考虑了前 i 个元素,当前选择了 j 个元素时的最小字符串,转移为 f_{i,j} \gets \min(f_{i-1,j},f_{i-1,j-1} S_i)。

这个 DP 还是错的,仍然没有考虑长度变化带来的问题。如 [\tt{b},\tt{ba},\tt{c}]。但是我们发现字典序是正序比较的,如果倒序 DP 就不会有问题。

重设状态为:f_{i,j} 表示考虑了后 i 个元素,当前选择了 j 个元素时的最小字符串。转移为 f_{i,j} \gets \min(f_{i+1,j},S_i f_{i+1,j-1})。

视作 n,k,|S_i| 同阶,复杂度 O(n^4)。 :::::

:::::info[代码]

const int N = 55;
int n, k;
string s[N], f[N][N];

void _main() {
    cin >> n >> k;
    string inf(k, 'z' + 1);
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1, [](const string& a, const string& b) -> bool {
        return a + b < b + a;
    });
    fill(f[n] + 1, f[n] + k + 1, inf), f[n][1] = s[n];
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= k; j++) f[i][j] = min(f[i + 1][j], s[i] + f[i + 1][j - 1]);
    }
    cout << f[1][k];
} 

:::::

:::::success[另解] 其实正序 DP 是可以救活的。

考虑钦定长度,记 f_{i,j,l} 为考虑了前 i 个元素,当前选择了 j 个元素,当前字符串的长度为 l 时的最小字符串。

此时转移不会受到长度影响:f_{i,j,l} \gets \min(f_{i-1,j,l},f_{i-1,j-1,l-|S_i|} S_i)。

直接做的复杂度为 O(n^6),在本题可以冲过去。一些魔怔的方法是用线段树合并维护一下哈希,然后二分比较字典序,可以做到 O(n^4 \log^2 n)。

::::: ## [P13785 [eJOI 2022] Longest Unfriendly Subsequence](https://www.luogu.com.cn/problem/P13785) > 定义序列 $b_i$ 是优秀的,当且仅当 $\forall 1 \le j-i \le 2, b_i \ne b_j$。给出长为 $n$ 的序列 $a_i$,求 $a_i$ 中最长优秀子序列的长度。 > > 多测,$\sum n \le 2 \times 10^9$,$1 \le a_i \le 10^9$。 :::::success[题解] 显然有 $O(n^3)$ 的暴力,设 $f_{i,j}$ 表示以 $a_i$ 结尾,倒数第二位为 $a_j$ 的最长子序列,转移是简单的。 注意到一些子任务的值域很小,将 $i,j$ 两维都改成颜色,枚举下标,复杂度 $O(nV^2)$。 事实上,答案中 $b_i,b_{i+1}$ 中间的颜色数目是很少的。设其为 $k$,可发现 $k \le 5$。证明考虑反证法。 因此,决策点实际上只有 $k$ 个,随便用个 deque 维护一下即可。实现的时候注意要放入一个颜色的最新位置,然后记一下上一个决策点的颜色,可以做到 $O(nk^2)$。 ::::: :::::info[代码] ```cpp line-numbers const int N = 2e5 + 5; int n, m, a[N], d[N], last[N], f[15][N], col[15][N]; deque<int> q; void _main() { fill(last + 1, last + m + 1, -1), q.clear(); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], d[i] = a[i]; sort(d + 1, d + n + 1), m = unique(d + 1, d + n + 1) - d - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(d + 1, d + m + 1, a[i]) - d; for (int i = 0; i <= 5; i++) fill(f[i] + 1, f[i] + n + 1, 1), fill(col[i] + 1, col[i] + n + 1, -1); q.emplace_back(1), last[a[1]] = 1; for (int i = 2; i <= n; i++) { auto it = find(q.begin(), q.end(), last[a[i]]); if (it != q.end()) { q.erase(it); q.emplace_back(i); } else { q.emplace_back(i); if (q.size() > 5) q.pop_front(); } last[a[i]] = i; for (int j = 0; j < (int) q.size(); j++) { col[j][i] = a[q[j]]; if (a[q[j]] == a[i]) continue; for (int k = 0; k <= 5; k++) { if (col[k][q[j]] == a[i]) continue; f[j][i] = max(f[j][i], f[k][q[j]] + 1); } } } int res = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= 5; j++) res = max(res, f[j][i]); } cout << res << '\n'; } ``` ::::: ## [P13692 [CEOI 2025] lawnmower](https://www.luogu.com.cn/problem/P13692) > 题意见原题题面。5 秒,1024 MB。 :::::success[题解] 首先写一个暴力 DP,记 $f_{i,x}$ 为处理完第 $i$ 个位置后,当前收集箱中有 $x$ 单位草时的最小代价。讨论一下转移: - 一次处理完成:对于 $x \le c-v_i$,转移 $f_{i-1,x}+a_i \to f_{i,x+v_i}$; - 多次处理完成:对于 $x>c-v_i$,此时需要处理 $w=v_i+x$ 单位,次数为 $k=\lfloor \frac{w-1}{c} \rfloor+1$,转移 $f_{i-1,x}+a_i k+b(k-1) \to f_{i,(w-1) \bmod c+1}$; - 清空收集箱:$f_{i,x}+b \to f_{i,0}$。 答案即 $f_{n,0}$。初值为 $f_{0,0} \gets 0$,剩余位置设为 $\infty$。复杂度 $O(nc)$,可以获得 [25pts](https://www.luogu.com.cn/record/272451629)。 考虑优化这个 DP。首先需要缩减状态数,观察一下转移,有效状态只能继承上一轮主动清空,或者这一轮主动清空,第 $i$ 轮转移只会有 $i+1$ 个有效位置。 接下来观察转移。我们发现第一条转移本质是第二条的特殊情形,故只需关注 $f_{i-1,x}+a_i k+b(k-1) \to f_{i,(w-1) \bmod c+1}$。进一步,我们发现本质不同的 $k$ 其实只有 $2$ 种。 记 $p=\lfloor \frac{v_i-1}{c} \rfloor,q=v_i \bmod c$,则下标偏移和 $k$ 的取值只有两类: - 若 $x \le c-q$,则转移后 $x\to x+q$,代价增加 $a_i(p+1)+b_ip$; - 若 $x>c-q$,转移后 $x \to x+q-c$,代价增加 $a_i(p+2)+b_i(p+1)$。 左侧原本的范围为 $[1,c-q]$,转移后的范围为 $[q+1,c]$;右侧原本的范围为 $(c-q,c]$,转移后的范围为 $[1,q]$。 可以用 FHQ-Treap 维护二元组 $(x,f_{x})$。以 $x$ 为关键字将树 $T$ 分裂为 $T_1,T_2$,然后将两棵树打上加标记,再将 $T_2,T_1$ 反向合并作为 $T$。 一点细节是单独处理 $f_{i,x}+b \to f_{i,0}$ 的转移。我们维护一下全局的 $f_{\min}$,然后用一个变量来记录当前的 $f_{i,0}$。下一轮转移时,将 $f_{i-1,0}$ 的后继插入 treap 中。 总复杂度 $O(n \log n)$。线段树优化也是可行的,但要维护下标偏移量,细节更多,所以推荐平衡树写法。 ::::: :::::info[代码] ```cpp line-numbers const i64 inf = 2e18; struct node { u32 pri; node *l, *r; i64 x, f, fmin, xtag, ftag; node(i64 _x, i64 _f) : pri(rand32()), l(nullptr), r(nullptr), x(_x), f(_f), fmin(_f), xtag(0), ftag(0) {} node* pushup() { return fmin = min({f, l ? l->fmin : inf, r ? r->fmin : inf}), this; } void apply(i64 xt, i64 ft) {x += xt, f += ft, fmin += ft, xtag += xt, ftag += ft;} void pushdown() { if (!xtag && !ftag) return; if (l) l->apply(xtag, ftag); if (r) r->apply(xtag, ftag); xtag = ftag = 0; } }; node* merge(node* u, node* v) { if (!u || !v) return u ? u : v; u->pushdown(), v->pushdown(); return (u->pri < v->pri) ? (u->r = merge(u->r, v), u->pushup()) : (v->l = merge(u, v->l), v->pushup()); } void split(node* u, int k, node*& x, node*& y) { if (!u) return x = y = nullptr, void(); u->pushdown(); if (u->x <= k) x = u, split(u->r, k, u->r, y), x->pushup(); else y = u, split(u->l, k, x, u->l), y->pushup(); } i64 mow(int n, int c, int b, vector<int> &a, vector<int> &v) { node *rt = nullptr; i64 f0 = 0; for (int i = 0; i < n; i++) { i64 p = (v[i] - 1) / c, q = v[i] % c; if (q == 0) q = c; if (rt) { node *x, *y; split(rt, c - q, x, y); if (x) x->apply(q, a[i] * (p + 1) + b * p); if (y) y->apply(q - c, a[i] * (p + 2) + b * (p + 1)); rt = merge(y, x); } node *x, *y; split(rt, q, x, y); rt = merge(merge(x, new node(q, f0 + a[i] * (p + 1) + b * p)), y); f0 = rt->fmin + b; } return f0; } ``` ::::: ## 【无题解】[P9870 [NOIP2023] 双序列拓展](https://www.luogu.com.cn/problem/P9870) ## [P5979 [PA 2014] Druzyny](https://www.luogu.com.cn/problem/P5979) > 给出 $n$ 个物品,每个物品有属性 $l_i,r_i$,你需要将它们划分为若干连续段,满足第 $i$ 个物品所属连续段长度 $\in [l_i,r_i]$。 > > 求出最大段数和达成此段数的方案数,或者报告无解。方案数对 $10^9+7$ 取模。 > > $n \le 10^6$,**7 秒**,256 MB。 :::::success[题解] 容易设计一个朴素 DP,设 $f_i$ 为以 $i$ 结尾的最大段数,枚举上一段结束点 $j$ 有 $$ f_i=1+\max_{j\le i, \forall k \in [j,i], j-i+1 \in [l_k,r_k]} f_j $$ 方案数容易根据 $f$ 的转移同时维护,下面只对 $f$ 的求解考虑。 将 $\forall k \in [j,i], j-i+1 \in [l_k,r_k]$ 单独拿出来看,发现只需取交集,即条件等价于 $j-i+1 \in \bigcap\limits_{k \in[j,i]} [l_k,r_k]$。记 $L(j,i)=\max\limits_{k \in [j,i]} l_k, R(j,i)=\max\limits_{k \in [j,i]} r_i$,则交集 $S(j,i)=[L(j,i),R(j,i)]$。通过倒序枚举 $j$ 维护交集可做到 $O(n^2)$,获得 [46 分](https://www.luogu.com.cn/record/266599515)。 DP 式不满足决策单调性,$j$ 的取值也不连续,只能考虑 CDQ 分治优化 DP。计算出左段 $[l,m]$ 的 DP,我们考虑其对 $(m,r]$ 中每个点的影响。 将点对 $(i,j)$ 有影响的条件列出: - $i \in [l,m] \land j \in (m,r]$。 - $j-i+1 \in S(i,j)$。 本题最为精妙的点在于将第二个条件按照 $m$ 拆开: - $j-i+1 \in S(i,j) \iff j-i+1 \in S(i,m) \land j-i+1 \in S(m+1,j)$。 第一个条件关于 $i$,第二个条件关于 $j$,形成了一个二维数点结构,考虑扫描线。这里的扫描线比较巧妙,展开叙述一下: 把一个 $i$ 产生贡献和贡献消失的信息挂到下标上。对序列开一棵线段树,支持单点修改,区间求 max。则 $j$ 对于 $i$ 会被影响的下标也是一段区间,可以直接在线段树上求出。 复杂度 $O(n \log^2 n)$,在 7s 下足以通过。 ::::: :::::info[代码] ```cpp line-numbers const int N = 1e6 + 5, inf = 1e9; int n, a[N], b[N]; using node = pair<int, mint>; node operator+ (const node& a, const node& b) { if (a.first != b.first) return max(a, b); return {a.first, a.second + b.second}; } int tot; struct segtree { #define ls (rt << 1) #define rs (rt << 1 | 1) node sum[N << 2]; void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];} void build(int l = 0, int r = tot, int rt = 1) { sum[rt] = node(-inf, 0); if (l == r) return; int mid = (l + r) >> 1; build(l, mid, ls), build(mid + 1, r, rs); } void change(int x, const node& c, int l = 0, int r = tot, int rt = 1) { if (l == r) return sum[rt] = c, void(); int mid = (l + r) >> 1; if (x <= mid) change(x, c, l, mid, ls); else change(x, c, mid + 1, r, rs); pushup(rt); } node ask(int tl, int tr, int l = 0, int r = tot, int rt = 1) { if (tl <= l && r <= tr) return sum[rt]; int mid = (l + r) >> 1; if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs); return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs); } } sgt; node dp[N]; vector<pair<int, int>> vec[N]; void solve(int l, int r) { if (l == r) return; int mid = (l + r) >> 1; solve(l, mid); for (int i = mid + 1; i <= r; i++) vec[i].clear(); for (int i = mid, cl = 1, cr = n; i >= l; i--) { if (cl > cr || i + cr <= mid) break; if (i + cl <= r) { vec[max(mid + 1, i + cl)].emplace_back(i, 1); vec[min(r + 1, i + cr + 1)].emplace_back(i, -1); } cl = max(cl, a[i]), cr = min(cr, b[i]); } tot = mid - l + 1, sgt.build(); for (int i = mid + 1, cl = 1, cr = n; i <= r; i++) { for (auto& [x, op] : vec[i]) { if (op == 1) sgt.change(x - l + 1, dp[x]); else sgt.change(x - l + 1, node(-inf, 0)); } cl = max(cl, a[i]), cr = min(cr, b[i]); if (cl > cr || i - cr > mid) break; int ql = max(l, i - cr) - l + 1, qr = min(mid, i - cl) - l + 1; if (ql > qr) continue; node u = sgt.ask(ql, qr); dp[i] = dp[i] + node(u.first + 1, u.second); } solve(mid + 1, r); } void _main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i]; fill(dp + 1, dp + n + 1, node(-inf, 0)); dp[0] = node(0, 1), solve(0, n); auto [f, g] = dp[n]; if (g.val == 0) cout << "NIE"; else cout << f << ' ' << g; } ``` :::::