算法动态规划

倍增优化DP

字数统计: 2.6k字   |   阅读时长: 12分
, , ,

摘要: 倍增优化DP，减少状态个数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 倍增法 中我们了解了倍增法的原理与实现。本文我们以力扣 466 来看一下倍增优化 DP，最后我们解决一个非常困难的问题。

倍增优化DP

在动态规划的状态推导中，一般情况下状态是线性增长的，但有时候状态可以成倍增长。状态成倍增长的推导过程分为一下两步：

  • 预处理: 状态成倍增长的 DP，计算出 $2^{k}$ 的状态 dp[k]
  • 拼凑：基于二进制划分思想，用 dp[k] 组合成最终答案

上面这种通过预处理和拼凑两部分实现状态的成倍增长的过程，称为倍增优化 DP。

模板题

下面这道题有倍增优化DP、循环节优化技巧、序列自动机等做法，参考文章 【DP难题】力扣466-统计重复个数。本文我们主要看一下倍增优化 DP 的做法。

由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，[“abc”,3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，”abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 1 <= n1 <= 1e6 和 1 <= n2 <= 1e6。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

1
2
3
4
5
6
1 <= N <= 1e5,
1 <= M <= 1e4,
−1e9 <= Hi <= 1e9,
0 <= X0 <= 1e9,
1 <= Si <= N,
0 <= Xi <= 1e9，

算法: 倍增优化DP

给定 s1 上的起始点 i，能往前匹配多少个 s2 是确定的，记为 C，因为每个 s2 都是在往右推进无法回头的，因此可以二分 s2 的个数，问匹配这么多个 s2 是否超出 n1 个 s1 的范围了。

因此可以预处理重 dp[i][k] := 起点为 i，匹配 $2^{k}$ 个 s2 所需的长度，终点为 (i + dp[i][k]) % len1。然后用二进制划分的方式凑出 C。

1
2
dp[i][k] := 起点为 i，匹配 2^k 个 s2 所需的长度
dp[i][k] = dp[i][k - 1] + dp[(i + dp[i][k - 1]) % len1][k - 1]

代码 (C++)

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
class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        using ll = long long;
        int len1 = s1.size(),len2 = s2.size();
        const int K = 30;
        vector<vector<ll>> dp(len1, vector<ll>(K, 0));
        int l1 = 0,l2 = 0;
        for(int i = 0; i < len1; ++i)
        {
            l1 = i; l2 = 0;
            while(l2<len2)
            {
                while(l1 < n1 * len1 && s1[l1 % len1] != s2[l2])
                    l1++;
                l1++;
                l2++;
            }
            dp[i][0] = l1 - i;
        }
        for(int k = 1; k < K; ++k)
            for(int i = 0; i < len1; ++i)
            {
                dp[i][k] = dp[i][k - 1] + dp[(i + dp[i][k - 1]) % len1][k - 1];
            }
        long long int ans = 0;
        int begin = 0;
        for(int k = 29; k >= 0; k--)
            while((begin + dp[(begin % len1)][k]) <= n1 * len1)
            {
                ans += (1 << k);
                begin += dp[(begin % len1)][k];
            }
        return ans / n2;
    }
};

题目

给定起始点 i，能往前走多少天是固定的(两个人轮流，一人一天)，记为 T，因为每天都往一个方向走不能回头，因此可以二分天数，问从该起点走这么多天数是否超出地图范围了。

因此可以预处理出 dp[i][k] := 起点为 i，走 $2^{k}$ 天将到达的终点，如果超出范围用一个特殊数字标记。然后用二进制划分的方式凑出 T。

算法：倍增优化DP

计算过程中城市编号均从 0 开始，返回答案时再加 1。

step1：预处理从城市 i 出发，沿前进方向，按照规则的下一个城市。预处理过程可以用 TreeMap。

1
2
nxt1[i] := 从编号 i 的城市出发，下一个最近城市的编号。
nxt2[i] := 从编号 i 的城市出发，下一个次近城市的编号。

step2：预处理从城市 j 出发，一共刚好行驶 i 天，k 先开车的情况下的以下三个信息：

  • 到达的城市 dp[i][j][k]
  • A 的行驶距离 dpa[i][j][k]
  • B 的行驶距离 dpb[i][j][k]

状态需要持有的信息：所在城市，已经行驶的天数，A 行驶的距离，B 行驶的距离。

将行驶天数作为阶段，所在城市，A 行驶的距离，B 行驶的距离为状态，对行驶天数 i 倍增优化

倍增后的阶段 i 在状态转移时为 dp[i][...] = dp[i - 1][...] + dp[i - 1][...]。
依据: $2^{i} = 2^{i-1} + 2^{i-1}$

1
2
3
4
5
6
7
dp[i][j][k] := 从城市 j 出发, 共行驶 2^i 天，k 先开车，最终会到达的城市
初始化
dp[0][j][0] = nxt1[j]
dp[0][j][1] = nxt2[j]
转移
dp[1][j][k] = dp[0][dp[0][j][k]][1 - k]
dp[i][j][k] = dp[i - 1][dp[i - 1][j][k]][k] i > 1
1
2
3
4
5
6
7
dpa[i][j][k] := 从城市 j 出发，共行驶 2^i 天，k 先开车，A 行驶的距离
初始化
dpa[0][j][0] = abs(H[j] - H[nxt1[j]])
dpa[0][j][1] = 0
转移
dpa[1][j][k] = dpa[0][j][k] + dpa[0][dp[0][j][k]][1 - k]
dpa[i][j][k] = dpa[i - 1][j][k] + dpa[i - 1][dp[i - 1][j][k]][k] i > 1
1
2
3
4
5
6
7
dpb[i][j][k] := 从城市 j 出发，共行驶 2^i 天，k 先开车，B 行驶的距离
初始化
dpb[0][j][0] = 0
dpb[0][j][1] = abs(H[j] - H[nxt2[j]])
转移
dpb[1][j][k] = dpb[0][j][k] + dpb[0][dp[0][j][k]][1 - k]
dpb[i][j][k] = dpb[i - 1][j][k] + dpb[i - 1][dp[i - 1][j][k]][k] i > 1

边界：

1
nxt1[j], nxt2[j], dp[i][j][k] 为 -1 时表示已经超过 N 个城市的范围

已有的是行驶天数为 $2^i$

step3：计算给定起点 S，最多行驶 X 时，A 和 B 的行驶距离：

la, lb = solve(S, X)

记到达终点行驶的天数为 K，递减顺序枚举所有 $2^{i}$，作为行驶天数，用二进制划分的思想拼出 K。

从起点开始，尝试往前走，当前的尝试为 i，如果向前走 $2^{i}$ 步可以到达合法城市，且总距离没有超过 X，则 $2^[i]$ 是 K 的一部分，否则不是 K 的一部分。

1
2
3
4
5
初始化 A, B 行驶的距离, la = 0, lb = 0，初始化当前城市 p = S
for(i = logN; i >= 0; --i):
    若从 p 出发行驶 2^i 天，累计路程未超过 X
    即 la + lb + dpa[i][p][0] + dpb[i][p][0] <= X
    则 la += dpa[i][p][0], lb += dpb[i][p][0], p = dp[i][p][0]

step4：计算给定 X0 时，从哪个点出发，A 行驶距离比上 B 行驶距离最小。

枚举起点 Si，计算 la, lb = solve(Si, X0)，取 la / lb 最小值。

代码 (C++)

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

using ll = long long;
using PLI = pair<ll, int>;

const int N = 100010;
const int M = 17;
const ll INF = 1e12;

int n;
vector<int> H;
// nxt1[i] := 从编号 i 的城市出发，下一个最近城市的编号, -1 表示不存在
// nxt2[i] := 从编号 i 的城市出发，下一个次近城市的编号, -1 表示不存在
vector<int> nxt1, nxt2;
// dp[i][j][k] := 从城市 j 出发, 共行驶 2^i 天，k 先开车，最终会到达的城市
// dpa[i][j][k] := 从城市 j 出发，共行驶 2^i 天，k 先开车，A 行驶的距离
// dpb[i][j][k] := 从城市 j 出发，共行驶 2^i 天，k 先开车，B 行驶的距离
int dp[M][N][2];
int dpa[M][N][2], dpb[M][N][2];

void init_g()
{
    nxt1.assign(n + 1, 0);
    nxt2.assign(n + 1, 0);
    set<PLI> S;
    S.insert({INF, 0});
    S.insert({INF + 1, 0});
    S.insert({-INF, 0});
    S.insert({-INF - 1, 0});

    for(int i = n; i >= 1; --i )
    {
        PLI t(H[i], i);
        auto j = S.lower_bound(t);
        ++j;
        vector<PLI> cand;
        for(int k = 0; k < 4; ++k)
        {
            cand.push_back(*j);
            --j;
        }
        ll d1 = INF, d2 = INF;
        int p1, p2;
        for(int k = 3; k >= 0; --k)
        {
            ll d = abs(H[i] - cand[k].first);
            if(d < d1)
            {
                d2 = d1;
                d1 = d;
                p2 = p1;
                p1 = cand[k].second;
            }
            else if(d < d2)
            {
                d2 = d;
                p2 = cand[k].second;
            }
        }
        S.insert(t);
        nxt1[i] = p2;
        nxt2[i] = p1;
    }
}

void init_f()
{
    for(int i = 0; i < M; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == 0)
            {
                dp[0][j][0] = nxt1[j];
                dp[0][j][1] = nxt2[j];
            }
            else
            {
                for(int k = 0; k < 2; ++k)
                {
                    if(i == 1)
                        dp[1][j][k] = dp[0][dp[0][j][k]][1 - k];
                    else
                        dp[i][j][k] = dp[i - 1][dp[i - 1][j][k]][k];
                }
            }
        }
}

int get_dist(int a, int b)
{
    return abs(H[a] - H[b]);
};

void init_d()
{
    for(int i = 0; i < M; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(i == 0)
            {
                dpa[0][j][0] = get_dist(j, nxt1[j]);
                dpa[0][j][1] = 0;
                dpb[0][j][1] = get_dist(j, nxt2[j]);
                dpb[0][j][0] = 0;
            }
            else
            {
                for(int k = 0; k < 2; ++k)
                {
                    if(i == 1)
                    {
                        dpa[1][j][k] = dpa[0][j][k] + dpa[0][dp[0][j][k]][1 - k];
                        dpb[1][j][k] = dpb[0][j][k] + dpb[0][dp[0][j][k]][1 - k];
                    }
                    else
                    {
                        dpa[i][j][k] = dpa[i - 1][j][k] + dpa[i - 1][dp[i - 1][j][k]][k];
                        dpb[i][j][k] = dpb[i - 1][j][k] + dpb[i - 1][dp[i - 1][j][k]][k];
                    }
                }
            }
        }
}

void calc(int p, int X, int& la, int& lb)
{
    la = 0;
    lb = 0;
    for(int i = M - 1; i >= 0; --i)
    {
        if(dp[i][p][0] > 0 && la + lb + dpa[i][p][0] + dpb[i][p][0] <= X)
        {
            la += dpa[i][p][0];
            lb += dpb[i][p][0];
            p = dp[i][p][0];
        }
    }
}

int main()
{
    cin >> n;
    H.assign(n + 1, 0);
    for(int i = 1; i <= n; ++i)
        cin >> H[i];

    init_g();
    init_f();
    init_d();

    int X0;
    cin >> X0;
    int res = 0, max_h = 0;
    double min_ratio = INF;
    for(int i = 1; i <= n; ++i)
    {
        int la, lb;
        calc(i, X0, la, lb);
        double ratio = lb != 0 ? (double)la / lb : INF;
        if(ratio < min_ratio || (ratio == min_ratio && H[i] > max_h))
        {
            min_ratio = ratio;
            max_h = H[i];
            res = i;
        }
    }
    cout << res << endl;

    int m;
    cin >> m;
    for(int i = 0; i < m; ++i)
    {
        int s, x;
        cin >> s >> x;
        int la, lb;
        calc(s, x, la, lb);
        cout << la << " " << lb << endl;
    }
}
Share