1. 云图网首页
  2. 技术专区
  3. 编程笔记

DP专题-学习笔记+专项训练：数据结构优化 DP

• 编程笔记


目录

1. 前言

数据结构优化 DP，是利用各种数据结构来优化 DP 的时空复杂度的一种方法。

前置知识：普通 DP+常见数据结构（比如线段树等）

注意本篇博文将不会对暴力 DP 方程如何建立进行讲解。

2. 例题

例题：P4644 [USACO05DEC]Cleaning Shifts S

数据结构优化 DP 分四步：

  1. 写出转移方程。
  2. 观察整理式子。
  3. 数据结构优化。
  4. 一些细节处理。

其实一般 DP 的优化题目都是这样的。

在这道题上说明一下。

  1. 写出转移方程

设题中所求区间为 /([s,t]/)。

设 /(f_i/) 表示当 /([s,l_i]/) 都被覆盖（有奶牛工作）时的最小花费。

那么我们可以写出如下的转移方程（/(val_i/) 是第 /(i/) 头牛的花费）：

/[f_{r_i}=/min/limits_{l_i-1 /leq j /leq r_i-1}/{f_j+val_i/}
/]

复杂度为 /(O(n^2)/)，初值 /(f_{s-1}=0/)，其余为 /(INF/)。

  1. 观察整理式子

观察转移式子，我们发现 /(val_i/) 是跟 /(j/) 无关的项，提出来：

/[f_{r_i}=/min/limits_{l_i-1 /leq j /leq r_i-1}/{f_j/}+val_i
/]

需要注意的是，如果你一开始写的方程就是上面的方程，那么这一步对你来说是无效的。

  1. 数据结构优化

观察 /(/min/limits_{l_i-1 /leq j /leq r_i-1}/{f_j/}/) 这一项，我们会发现这实际上就是一个区间求最小值的问题。

区间求最小值？线段树嘛！

注意这个地方不能使用不带修改的数据结构维护（如 st 表），因为在算完 /(f_i/) 之后还要单点修改。

区查单改，妥妥的线段树模板~

于是拿线段树维护一下，复杂度降至 /(O(n /log n)/)。

  1. 一些细节处理

注意输入的 /(a/) 需要按照右端点排序，否则算法不正确（具有后效性）。

由于时间从 0 开始，可能会出现 /(s-1=-1/) 的现象，需要对所有时间 +1。

代码：

/*
========= Plozia =========
    Author:Plozia
    Problem:P4644 [USACO05DEC]Cleaning Shifts S
    Date:2021/5/6
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 10000 + 10, MAXT = 86399 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, s, t;
LL f[MAXT];
struct node { int l, r; LL val; } a[MAXN];
struct node1
{
    int l, r;
    LL minn;
    #define l(p) tree[p].l
    #define r(p) tree[p].r
    #define m(p) tree[p].minn
}tree[MAXT << 2];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
bool cmp(const node &fir, const node &sec) { return fir.r < sec.r; }
LL Min(LL fir, LL sec) { return (fir < sec) ? fir : sec; }
LL Max(LL fir, LL sec) { return (fir > sec) ? fir : sec; }

void build(int p, int l, int r)//建树
{
    l(p) = l, r(p) = r;
    if (l == r) { m(p) = INF; return ; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
    m(p) = Min(m(p << 1), m(p << 1 | 1));
}

void change(int p, int x, LL d)//单点修改
{
    if (l(p) == r(p) && l(p) == x) { m(p) = Min(m(p), d); return ;}
    int mid = (l(p) + r(p)) >> 1;
    if (x <= mid) change(p << 1, x, d);
    else change(p << 1 | 1, x, d);
    m(p) = Min(m(p << 1), m(p << 1 | 1));
}

LL ask(int p, int l, int r)//区间查询
{
    if (l(p) >= l && r(p) <= r) return m(p);
    int mid = (l(p) + r(p)) >> 1; LL val = INF;
    if (l <= mid) val = Min(val, ask(p << 1, l, r));
    if (r > mid) val = Min(val, ask(p << 1 | 1, l, r));
    return val;
}

int main()
{
    n = read(), s = read() + 1, t = read() + 1;
    for (int i = 1; i <= n; ++i) a[i].l = Max(read() + 1, s), a[i].r = Min(read() + 1, t), a[i].val = (LL)read();
    std::sort(a + 1, a + n + 1, cmp);//排序
    build(1, 0, t); memset(f, 0x3f, sizeof(f)); f[s - 1] = 0; change(1, s - 1, 0);//初始化
    for (int i = 1; i <= n; ++i)
    {
        LL sum = ask(1, a[i].l - 1, a[i].r - 1);
        if (sum == INF) continue ;
        f[a[i].r] = sum + a[i].val;
        change(1, a[i].r, f[a[i].r]);
    }//转移
    if (f[t] == INF) printf("-1/n");
    else printf("%lld/n", f[t]);
    return 0;
}

3. 练习题

题单：

CF597C Subsequences

  1. 写出转移方程

设 /(f_{i,j}/) 表示以 /(i/) 为末尾，长度为 /(j/) 的最长上升子序列的方案数，那么有转移方程：

/[f_{i,j}=/sum_{k=1}^{i-1}f_{k,j-1}(a_k<a_i)
/]

复杂度 /(O(n^2k)/)，初值为 /(f_{i,1}=1|i /in [1,n]/)。

  1. 观察整理式子

没法整理qwq

  1. 数据结构优化

观察 /(/sum/limits_{k=1}^{i-1}f_{k,j-1}(a_k<a_i)/)，我们发现：我们需要在 /([1,i-1]/) 中查询所有 /(a_k<a_i/) 的 /(k/) 的 /(f_{k,j-1}/) 的和好绕口。

那么这个仍然可以使用线段树优化。

我们建立 /(k/) 棵线段树（这里的 /(k/) 是题中的 /(k/) 加 1），第 /(i/) 棵线段树专门用来维护 /(f_{j,i}|j /in [1,n]/)。

注意线段树是值域线段树。

然后对于第 /(i/) 个位置的数，转移完之后在 /(a_i/) 上单点加上 /(f_{i,j}/) 即可，而转移可以采用线段树的区间查询。

  1. 一些细节处理

没啥细节qwq

代码：

/*
========= Plozia =========
    Author:Plozia
    Problem:CF597C Subsequences
    Date:2021/5/9
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 1e5 + 10;
int n, k, a[MAXN];
LL f[MAXN][15];
struct node
{
    int l, r;
    LL val;
}tree[15][MAXN << 2];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}

void build(int p, int Tag, int l, int r)
{
    tree[Tag][p].l = l, tree[Tag][p].r = r;
    if (l == r) { tree[Tag][p].val = 0; return ; }
    int mid = (l + r) >> 1;
    build(p << 1, Tag, l, mid); build(p << 1 | 1, Tag, mid + 1, r);
    tree[Tag][p].val = tree[Tag][p << 1].val + tree[Tag][p << 1 | 1].val;
}

void add(int p, int Tag, int x, LL d)
{
    if (tree[Tag][p].l == tree[Tag][p].r && tree[Tag][p].l == x) { tree[Tag][p].val += d; return ; }
    int mid = (tree[Tag][p].l + tree[Tag][p].r) >> 1;
    if (x <= mid) add(p << 1, Tag, x, d);
    else add(p << 1 | 1, Tag, x, d);
    tree[Tag][p].val = tree[Tag][p << 1].val + tree[Tag][p << 1 | 1].val;
}

LL ask(int p, int Tag, int l, int r)
{
    if (tree[Tag][p].l >= l && tree[Tag][p].r <= r) return tree[Tag][p].val;
    int mid = (tree[Tag][p].l + tree[Tag][p].r) >> 1; LL val = 0;
    if (l <= mid) val += ask(p << 1, Tag, l, r);
    if (r > mid) val += ask(p << 1 | 1, Tag, l, r);
    return val;
}

int main()
{
    n = read(), k = read() + 1;
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) f[i][1] = 1;
    for (int i = 1; i <= k; ++i) build(1, i, 1, n);
    for (int i = 1; i <= n; ++i)
    {
        add(1, 1, a[i], 1);
        for (int j = 2; j <= k; ++j) { f[i][j] = ask(1, j - 1, 1, a[i] - 1); add(1, j, a[i], f[i][j]); }
    }
    LL ans = 0;
    for (int i = 1; i <= n; ++i) ans += f[i][k];
    printf("%lld/n", ans); return 0;
}

P2605 [ZJOI2010]基站选址

  1. 写出转移方程

设 /(f_{i,j}/) 表示在前 /(i/) 个村庄当中选取了 /(j/) 个基站，且第 /(i/) 个基站必须被选中时的最小花费，不考虑后面的村庄。

这里为了方便，在 /(INF/) 远处设计一个基站，其中距离为 /(INF/)，建立花费为 0，范围为 0，赔偿费用为 /(INF/)，这样这个基站必须要被选中，共有 /(n+1/) 个基站。

设计转移方程如下：

/[f_{i,j}=/min/{f_{k,j-1}+Money_{k,i}|j<i/}
/]

其中 /(Money_{k,i}/) 表示当第 /(k/) 个村庄与第 /(i/) 个村庄被选中时，在这两个村庄之内的不被覆盖的村庄需要赔偿的总费用。

复杂度为 /(O(n^3k)/)，初值为 /(f_{i,1}=Cost_{i}+t/)，/(t/) 表示所有在 /(i/) 前面且不被覆盖的村庄需要赔偿的总费用。

答案为 /(/min/{f_{i,k}|i /in [1,n]/}/)。

  1. 观察整理式子

发现所有 /(f_{i,j}/) 只与 /(f_{k,j-1}/) 有关，因此可以使用滚动数组优化，方程如下：

/[f_{i}=/min/{f_{k}+Money_{k,i}|j<i/}
/]

  1. 数据结构优化

接下来到了最关键的一步：如何快速求出 /(f_{k}+Money_{k,i}/)？

首先使用两个辅助数组：/(left_i,right_i/)。

  • /(left_i/)：最左边的村庄使其能够覆盖到 /(i/)。
  • /(right_i/)：最右边的村庄使其能够覆盖到 /(i/)。

接下来我们需要知道有多少 /(right_i=k/)。

这个使用链式前向星 / vector 可以存下。

我们建立一棵线段树来维护 /(f_{k}+Money_{k,i}/)，查询就很简单了，就是一个前缀最小值查询。

那么如何修改呢？

对于第 /(i/) 个村庄，我们知道哪些村庄 /(j/) 满足 /(right_j=i/)。

既然如此，我们取出这些村庄，因为后面的所有村庄都不可能覆盖到这个村庄了，因此后面的村庄如果不从 /([left_i,right_i]/) 中转移，也就是从 /([1,left_{i}-1]/) 中转移，必定需要赔偿这些村庄。

因此我们对 /([1,left_i-1]/) 做一个区间加即可。

这样，原先的 /(O(n^3k)/) 的复杂度被成功的优化到了 /(O(nk /log n)/)。

  1. 一些细节处理
  • 注意每一次枚举 /(i/) 都需要重新建一遍树。
  • 注意对 /(right_i/) 的细节条件处理（具体看代码）。
  • 因为采用了滚动数组优化，因此在每一次枚举 /(i/) 之后都需要更新一遍答案。
  • 更新答案的时候注意 不要忘记初始的 /(f_n/)。

代码：

/*
========= Plozia =========
    Author:Plozia
    Problem:P2605 [ZJOI2010]基站选址
    Date:2021/5/9
========= Plozia =========
*/

#include <bits/stdc++.h>
#define int long long

typedef long long LL;
const int MAXN = 20000 + 10, INF = 0x7f7f7f7f;
int n, k, dis[MAXN], Cost[MAXN], Range[MAXN], pay[MAXN], left[MAXN], right[MAXN], Head[MAXN], cnt_Edge = 1, f[MAXN], ans;
struct node { int to, Next; } Edge[MAXN];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }
void add_Edge(int x, int y) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, Head[x]}; Head[x] = cnt_Edge; }

struct Segment_tree
{
    struct Tree
    {
        int l, r, sum, add;
        #define l(p) tree[p].l
        #define r(p) tree[p].r
        #define s(p) tree[p].sum
        #define a(p) tree[p].add
    }tree[MAXN << 2];
    void build(int p, int l, int r)
    {
        l(p) = l, r(p) = r, a(p) = 0;
        if (l == r) { s(p) = f[l]; return ; }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
        s(p) = Min(s(p << 1), s(p << 1 | 1));
    }
    void spread(int p)
    {
        if (a(p))
        {
            s(p << 1) += a(p); s(p << 1 | 1) += a(p);
            a(p << 1) += a(p); a(p << 1 | 1) += a(p);
            a(p) = 0;
        }
    }
    void add(int p, int l, int r, int k)
    {
        if (l > r) return ;
        if (l(p) >= l && r(p) <= r) { s(p) += k; a(p) += k; return ; }
        spread(p); int mid = (l(p) + r(p)) >> 1;
        if (l <= mid) add(p << 1, l, r, k);
        if (r > mid) add(p << 1 | 1, l, r, k);
        s(p) = Min(s(p << 1), s(p << 1 | 1));
    }
    int ask(int p, int l, int r)
    {
        if (l > r) return INF;
        if (l(p) >= l && r(p) <= r) return s(p);
        spread(p); int mid = (l(p) + r(p)) >> 1, val = INF;
        if (l <= mid) val = Min(val, ask(p << 1, l, r));
        if (r > mid) val = Min(val, ask(p << 1 | 1, l, r));
        return val;
    }
}Seg;

void Init()
{
    int sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        f[i] = sum + Cost[i];
        for (int j = Head[i]; j; j = Edge[j].Next) sum += pay[Edge[j].to];
    }
}

signed main()
{
    n = read(), k = read();
    for (int i = 2; i <= n; ++i) dis[i] = read();
    for (int i = 1; i <= n; ++i) Cost[i] = read();
    for (int i = 1; i <= n; ++i) Range[i] = read();
    for (int i = 1; i <= n; ++i) pay[i] = read();
    ++n; ++k; dis[n] = pay[n] = INF;
    for (int i = 1; i <= n; ++i)
    {
        left[i] = std::lower_bound(dis + 1, dis + n + 1, dis[i] - Range[i]) - dis;
        right[i] = std::lower_bound(dis + 1, dis + n + 1, dis[i] + Range[i]) - dis;
        if (dis[right[i]] > dis[i] + Range[i]) --right[i];
        add_Edge(right[i], i);
    }
    Init(); ans = f[n];
    for (int i = 2; i <= k; ++i)
    {
        Seg.build(1, 1, n);
        for (int j = 1; j <= n; ++j)
        {
            f[j] = Seg.ask(1, 1, j - 1) + Cost[j];
            for (int k = Head[j]; k; k = Edge[k].Next) Seg.add(1, 1, left[Edge[k].to] - 1, pay[Edge[k].to]);
        }
        ans = Min(ans, f[n]);
    }
    printf("%lld/n", ans); return 0;
}

4. 总结

数据结构优化大体分 4 步：

  1. 写出转移方程。
  2. 观察整理式子。
  3. 数据结构优化。
  4. 一些细节处理。

原创文章，作者：kirin，如若转载，请注明出处：https://blog.ytso.com/245333.html

赞 (0)
0
上一篇 2022年4月18日
下一篇 2022年4月18日

相关推荐

发表回复

登录后才能评论