Dynamic Programming on Intervals

Normal Problems

区间动态规划的一般形式：枚举长度（阶段），枚举左端点，需要的话再枚举分割点

Unlock the Padlock

Source:Google Kick Start 2022 Round B

一个滚轮密码锁由 \(n\)个滚轮组成，每个的范围都是 \([0, D-1]\)（循环），初始是 \(a_i\) 。

每次操作选取一个区间 \(1 \le l_i \le r_i\le n\) ，将区间内所有滚轮都向上或向下拨一个位置。

要求 \([l_i,r_i]\subseteq[l_{i+1},r_{i+1}]\) ，问最少多少次把所有位置都变成 \(0\) 。

区间只能扩张不能收缩，因此任意时刻拨动的区间内的数字一定要相同。

如果 \(D\) 很小，可以设 \(f[l][r][k]\) 表示区间 \([l,r]\) 都调成 \(k\) 的最小代价，直接 \(\mathcal O(n^2D^2)\) 求解。

那么什么时候区间能真的扩张？当且仅当区间内的值和 \(a_{l-1}\) 或 \(a_{r+1}\) 一样，才能向左或向右扩展一位。

因此 任意时刻操作区间的值一定和某个端点相同 ，设 \(f[l][r][0/1]\) 表示把 \([l,r]\) 都调成左/右端点的最小操作次数。

直接每次区间长度扩展 \(1\) 转移即可，复杂度 \(\mathcal O(n^2)\) 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 407

int testcase;

ll n, d, f[N][N][2], a[N];

inline ll dis(ll a, ll b) {
    ll w = abs(a - b);
    return min(w, d - w);
}

inline void getmin(ll &a, ll b) {a = (a < b ? a : b);}

inline void work() {
    n = rd(); d = rd();
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); 
        f[i][i][0] = f[i][i][1] = 0;
    }
    for (int len = 1; len < n; ++len) {
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            getmin(f[l - 1][r][0], f[l][r][0] + dis(a[l], a[l - 1]));
            getmin(f[l - 1][r][0], f[l][r][1] + dis(a[r], a[l - 1]));
            getmin(f[l][r + 1][1], f[l][r][0] + dis(a[l], a[r + 1]));
            getmin(f[l][r + 1][1], f[l][r][1] + dis(a[r], a[r + 1]));
        }
    }
  	ll ans = min(f[1][n][0] + dis(a[1], 0), f[1][n][1] + dis(a[n], 0));
    printf("Case #%d: %lld\n", ++testcase, ans);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

Sue 的小球

Source: SDOI2008

有 \(n\) 个球往下落，初始坐标是\(x_i\) ，高度是 \(h_i\) ，下落速度 \(v_i\) ，可以下落到正无穷。

初始坐标在 \(x_0\)，每秒可以向左/向右移动 \(1\)，经过某个球的坐标时就把这个球拿走，获得当前高度的得分。

问拿到所有球的前提下，最大得分是多少。

得分 \(=\sum h_i-\sum\) 下降的高度，考虑动态规划求 \(\min\sum\) 下降的高度。

问题变为第 \(i\) 个位置每秒会消耗 \(v_i\) ，到一个位置就会停止消耗，是关路灯这个模型。

考虑把坐标排序之后离散化，拿走的球一定是一个连续的区间，因此我们可以让状态停在某一个端点。

状态设计比较特殊：设 \(f[l][r][0/1]\) 表示把 \([l,r]\) 全部拿走，最后停在左/右端点，从开始到这个时刻的最小总消耗

那么考虑每次扩展一个位置，那么所耗的时间就是两点距离，每一秒的代价就是 \(\sum_{i\notin [l,r]} v_i\) （所有没接到的球）

需要注意把初始坐标离散化进去。枚举区间动态规划复杂度 \(\mathcal O(n^2)\) 。

#include <bits/stdc++.h>
using namespace std;
typedef double db;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1007
#define fr first
#define sc second

pair<int, double> p[N];

db ans, sum[N], f[N][N][2];

inline void getmin(db &a, db b) {a = (a < b ? a : b);}

int main() {
    int n = rd(), c = rd();
    for (int i = 1; i <= n; ++i) p[i].fr = rd(); 
    for (int i = 1; i <= n; ++i) ans += rd() / 1000.0;
    for (int i = 1; i <= n; ++i) p[i].sc = rd() / 1000.0;
    p[++n] = make_pair(c, 0);
    sort(p + 1, p + 1 + n);
    for (int l = 1; l <= n; ++l)
        for (int r = 1; r <= n; ++r)
            for (int k = 0; k < 2; ++k) f[l][r][k] = 1e18;
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + p[i].sc;
        if (p[i].fr == c) f[i][i][0] = f[i][i][1] = 0;
    }
    
    for (int len = 1; len < n; ++len) 
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            db rsum = sum[n] - sum[r] + sum[l - 1];
            getmin(f[l - 1][r][0], f[l][r][0] + (p[l].fr - p[l - 1].fr) * rsum);
            getmin(f[l - 1][r][0], f[l][r][1] + (p[r].fr - p[l - 1].fr) * rsum);
            getmin(f[l][r + 1][1], f[l][r][0] + (p[r + 1].fr - p[l].fr) * rsum);
            getmin(f[l][r + 1][1], f[l][r][1] + (p[r + 1].fr - p[r].fr) * rsum);
        }
    printf("%.3lf\n", ans - min(f[1][n][0], f[1][n][1]));
    return 0;
}

Cities

Source: The45th ICPC Asia Kunming Regional

有 \(n\) 个点，第 \(i\) 个点的颜色是 \(c_i\) ，保证每种颜色最多出现 \(15\) 次。

每次操作可以把一段连续且颜色相同的点都改成某个颜色，问最少操作多少次使得所有点颜色相同。

先把同样颜色且连续的缩成一段，这样相邻两两颜色都不同，假设有 \(m\) 段。

如果所有的颜色都不同的话，那么答案就是 \(m-1\) ，因为每次只能改颜色相同的。

但是序列中依旧有颜色相同的，因此需要动态规划求，设 \(f[l][r]\) 表示把 \([l,r]\) 变成相同的所需的最少次数。

转移考虑 \(c_l\) 有没有单独消耗一次合并：

如果单独消耗了一次就是 \(f[l][r] = f[l + 1][r] + 1\)
如果不消耗，那么枚举相同的另一个是 \(k\) ，那么 \(f[l][r] = f[l + 1][k - 1] + f[k][r] + 1\)

后面这个方程成立的原因是，我们发现操作总是可以等效到把区间变成和端点颜色相同。

需要缩点的原因是，后一种方程里的 \(+1\) 是为了把 \([l + 1][k - 1]\) 变成和 \(c_l\) 相同的，不缩会求错。

枚举区间，再枚举相同颜色，因为题目限制每种颜色最多出现 \(15\) 次，复杂度 \(O(15n^2)\) 。

#include <bits/stdc++.h>
using namespace std;
typedef double db;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

inline void getmin(int &a, int b) {a = (a < b ? a : b);}

#define N 5007

int a[N], f[N][N], lst[N], nxt[N];

inline void work() {
    int n = rd(), tot = 0;
    for (int i = 1, x; i <= n; ++i) {
        x = rd();
        if (!tot || x != a[tot]) a[++tot] = x;
        lst[i] = n + 1;
    }
    n = tot;
    for (int i = n; i; --i) {
        nxt[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    for (int len = 2; len <= n; ++len)
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            f[l][r] = f[l + 1][r] + 1;
            for (int j = nxt[l]; j <= r; j = nxt[j])
                getmin(f[l][r], f[l + 1][j - 1] + f[j][r] + 1);
        }
    printf("%d\n", f[1][n]);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

Dire Wolf

Source:2014 ICPC Asia Beijing Regional

有 \(n\) 个恐狼先锋排成一排，第\(i\) 个有 \(a_i\) 初始攻击力，并且会为两侧的恐狼临时增加 \(b_i\)攻击力（死了就没了）

每次杀掉一个需要承受他当前攻击力的伤害，问杀掉所有的狼，承受最少伤害是多少。

设 \(f[l][r]\) 表示把 \([l,r]\) 这个区间的所有狼杀掉所需的最小代价。

枚举最后一只杀掉的狼 \(k\) ，考虑此时他两侧的狼是谁？

答案是 \(l-1\) 和 \(r+1\) ，考虑区间 DP 的阶段性，我只需要杀死当前枚举的区间的狼，所以两侧的狼都没有死过。

所以最后一只狼的攻击力是 \(a_k+b_{l-1}+b_{r + 1}\) ，枚举 \(k\) 更新，复杂度是 \(\mathcal O(n^3)\) 的。 \[ f[l][r] = \min_{l\le k\le r} \bigg\{f[l][k-1]+f[k+1][r]+a_k+b_{l-1}+b_{r+1}\bigg\} \]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 207

int a[N], b[N], testcase;

ll f[N][N];

inline void work() {
    int n = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= n; ++i) b[i] = rd();
    b[n + 1] = 0;
    for (int len = 1; len <= n; ++len)
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            f[l][r] = 1e18;
            for (int p = l; p <= r; ++p) 
                f[l][r] = min(f[l][r], f[l][p - 1] + f[p + 1][r] + a[p] + b[l - 1] + b[r + 1]);
        }
    printf("Case #%d: %lld\n", ++testcase, f[1][n]);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

You Are the One

Source:2012 ICPC Asia Tianjin Regional Online

\(n\)个人排成一队依次入栈，任意时刻都可以按栈序弹出栈内的任意人数。

第 \(i\) 个人如果是第 \(k\) 个出场的，代价是 \(D_i\ast (k-1)\)，求所有人代价和最小可能是多少。

设 \(f[l][r]\) 表示序列里只有 \([l,r]\) 这些人（假设区间前后的人不存在），最小代价是多少。

观察这些人的出入栈的顺序，发现序列会被第一个人何时出栈划分为两个阶段。

第一个人第一个入栈，假设第 \(k\) 个出栈（他出栈前只压入第 \(2\sim k\) 个人）那么序列表现为：

第 \(2\sim k\) 个人出入栈，这些人前面没有其他人，代价是 \(f[l+1][l+k-1]\)
第一个人出栈，前面有 \(k-1\) 个人，代价是 \(D_l\ast(k-1)\)
第 \(k+1\sim n\) 个人出入栈，这些人前面都增加 \(k\) 个人，代价是 \(f[l+k][r]+\sum_{i=l+k+1}^rD_i\ast k\)

枚举 \(k\) 更新，复杂度是 \(\mathcal O(n^3)\) 的。 \[ f[l][r] =\min_{1\le k\le r-l+1} \bigg\\{f[l + 1][l + k-1]+D_l\ast(k-1)+f[l+k][r] + \sum_{i=l+k}^r D_i\ast k\bigg\\} \]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 107

int testcase;

ll d[N], sum[N], f[N][N];

inline void getmin(ll &a, ll b) {a = (a < b ? a : b);}

inline void work() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        d[i] = rd();
        sum[i] = sum[i - 1] + d[i];
    }
    for (int len = 2; len <= n; ++len)
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            f[l][r] = 1e18;
            for (int k = 1; k <= len; ++k) 
                getmin(f[l][r], f[l + 1][l + k - 1] + d[l] * (k - 1) + f[l + k][r] + (sum[r] - sum[l + k - 1]) * k);
        }
    printf("Case #%d: %lld\n", ++testcase, f[1][n]);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

二叉查找树

Source: NOI2009

给定 \(n\) 个节点的key,value,times ，修改一个点的 value 代价是\(K\) ，修改后要保证两两value 不同。

然后把这些点建出一个 Treap，定义访问代价 \(\sum_{i} depth_i\ast times_{i}\)，最小化修改代价 + 访问代价。

核心点是 key 不能修改，所以中序遍历是固定的，根左侧是左子树，根右侧是右子树。

考虑在中序遍历上做区间 DP ，枚举谁做根，那么根的 value 应当比左右子树的节点 value 要小。

所以状态里我们还要记一下当前子树的最小 value 是多少。

设 \(f[l][r][k]\) 表示中序遍历区间 \([l,r]\) 内的点建树，里面的点 value 权值 \(\ge k\) ，的最小代价。

如果这个点的权值不需要改（前提 \(value_{rt}\ge k\) ），那么子树里的权值要比他大 \[ f[l][r][k] = \min_{l\le rt\le r}\bigg\{f[l][rt - 1][value_{rt}]+f[rt + 1][r][value_{rt}] + \sum_{i=l}^r times_i\bigg\} \]
如果这个点权值需要改，那么子树的权值下界也是 \(k\) \[ f[l][r][k] = \min_{l\le rt\le r}\bigg\{f[l][rt - 1][k]+f[rt + 1][r][k] + \sum_{i=l}^r times_i + K\bigg\} \]

因为初始两两节点 value 就不同，而且可以调整成任意实数，所以方程中对子树权值的约束不用修改。

答案是 \(\min_k f[1][n][k]\) ，把权值离散化一下，DP 复杂度是 \(\mathcal O(n^4)\) 的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

vector<int> s;

unordered_map<int, int> tr;

#define N 73

struct node {int k, v, t;} c[N];

ll f[N][N][N], sumt[N];

inline void getmin(ll &a, ll b) {a = (a < b ? a : b);}

int main() {
    int n = rd(), w = rd();
    for (int i = 1; i <= n; ++i) c[i].k = rd();
    for (int i = 1; i <= n; ++i) s.push_back(c[i].v = rd());
    for (int i = 1; i <= n; ++i) c[i].t = rd();
    sort(s.begin(), s.end());
    int cnt = 0;
    for (auto i : s) tr[i] = ++cnt;
    for (int i = 1; i <= n; ++i) c[i].v = tr[c[i].v];
    sort(c + 1, c + 1 + n, [](node x, node y){return x.k < y.k;});
    for (int i = 1; i <= n; ++i) sumt[i] = sumt[i - 1] + c[i].t;

    for (int len = 1; len <= n; ++len) 
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            for (int k = 0; k <= n; ++k) {
                f[l][r][k] = 1e18;
                for (int rt = l; rt <= r; ++rt) {
                    if (c[rt].v >= k)
                        getmin(f[l][r][k], f[l][rt - 1][c[rt].v] + f[rt + 1][r][c[rt].v]);
                    getmin(f[l][r][k], f[l][rt - 1][k] + f[rt + 1][r][k] + w);
                }
                f[l][r][k] += sumt[r] - sumt[l - 1];
            }
        }
    ll ans = 1e18;
    for (int k = 0; k <= n; ++k) ans = min(ans, f[1][n][k]);
    printf("%lld\n", ans);
    return 0;
}

Pre-Order

Source :AtCoder Beginner Contest 252 G

定义 dfs序：从根开始，每次选择未访问过的最小儿子访问，每个点第一次被访问时记入序列尾。

现给定 dfs 序，问有多少棵树符合。 \(n\le500\)

考虑多叉树转二叉树（左儿子右兄弟，这是一个双射），那么要求就变为右儿子一定要小于父节点的编号。

设 \(f_{l, r}\) 表示 \([l,r]\) 这段区间，以 \(l\) 为根形成这样一棵二叉树的方案数。

枚举右儿子是 \(k\in[l + 1, r], a[k] > a[l]\) ，有转移 \(f_{l, r} = \sum_k f_{l,k - 1} \times f_{k, r}\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 507
#define mod 998244353

ll a[N], f[N][N];

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); f[i][i] = 1;
    }
    for (int len = 2; len < n; ++len) {
        for (int l = 2; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            f[l][r] = f[l + 1][r];
            for (int k = l + 1; k <= r; ++k)
                if (a[k] > a[l]) f[l][r] = (f[l][r] + 1ll * max(1ll, f[l + 1][k - 1]) * f[k][r]) % mod;
        }
    }
    printf("%lld\n", f[2][n]);
    return 0;
}

Algorithms

Dynamic Programming

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Codeforces Round #787 (Div. 3) Previous

AtCoder Grand Contest 001 Next