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)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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\} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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\\} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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)\) 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}