写在前面
$ DP $，是每个信息学竞赛选手所必会的算法，而 $ DP $ 中状态的转移又显得尤为关键。本文主要从状态的设计和转移入手，利用各种方法对朴素 $ DP $ 的时间复杂度和空间复杂度进行优化与处理，以达到满足题目要求的目的；
参考文献：
动态规划算法的优化技巧 毛子青
c++ DP总结
《算法竞赛进阶指南》
一. 环形与后效性处理
我们都知道，一个题能用 $ DP $ 来解，需要满足以下两个性质：
- 无后效性
- 最优子结构
但对于有些题目，如果要用 $ DP $ 解决的话，会出现环形与后效性的问题；
所谓环形与后效性，即状态的转移与 $ DP $ 的方向并不完全一致；
举个例子，状态的转移可以从左到右，也可以从右到左，但 $ DP $ 的方向只能为从左到右或从右到左，此时称此 $ DP $ 为有后效性；
当状态初能够由状态末转移而来（此时构成了一个环形）时，此时称此 $ DP $ 为环形；
对于前者的处理，我们通常会改变 $ DP $ 的遍历方向，使其能够与状态转移的方向一致，当无法一致时，可以使用迭代的方法取得最优解；
对于后者，我们通常对初始状态分类讨论，找出几种不是环形的 $ DP $，破环成链，分别处理，最后取最优解；
例题
后效性
本题的高斯消元解法不再叙述，考虑 $ DP $；
设 $ f[i][j] $ 表示从最后一行走到点 $ (i, j) $ 所需的期望步数，则有状态转移方程：
\[\begin{equation} f[i][j] \ \begin{cases} \frac{f[i][1] + f[i + 1][1]}{2} + 1 \ (m = 1) \\ \frac{f[i + 1][j] + f[i][j + 1] + f[i][j]}{3} + 1 \ (j == 1) \\ \frac{f[i][j - 1] + f[i + 1][j] + f[i][j]}{3} + 1 \ (j = m) \\ \frac{f[i][j] + f[i + 1][j] + f[i][j - 1] + f[i][j + 1]}{4} + 1 \ (其他情况) \\ \end{cases} \end{equation} \]显然，我们 $ DP $ 的方向是向上的，但状态转移的方向是上下左右都有的，所以有后效性，要迭代；
#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
int n, m;
int xx, yy;
double f[1005][1005];
int main() {
cin >> n >> m;
cin >> xx >> yy;
if (xx == n) {
cout << "0.0000000000";
return 0;
}
for (int i = n - 1; i >= xx; i--) {
int tt = 65;
while(tt--) {
if (m == 1) {
f[i][1] = 0.5 * f[i][1] + 0.5 * f[i + 1][1] + 1;
} else {
for (int j = 1; j <= m; j++) {
if (j == 1) {
f[i][j] = 1.0 / 3 * f[i + 1][j] + 1.0 / 3 * f[i][j + 1] + 1.0 / 3 * f[i][j] + 1;
} else if (j == m) {
f[i][j] = 1.0 / 3 * f[i][j - 1] + 1.0 / 3 * f[i + 1][j] + 1.0 / 3 * f[i][j] + 1;
} else {
f[i][j] = 0.25 * f[i][j] + 0.25 * f[i + 1][j] + 0.25 * f[i][j - 1] + 0.25 * f[i][j + 1] + 1;
}
}
}
}
}
cout << fixed << setprecision(4) << f[xx][yy];
return 0;
}
环形
设计状态 $ f[i][j][k] $ 表示在每 $ N $ 个小时的前 $ i $ 个小时中，休息 $ j $ 个小时，且第 $ j $ 个小时的状态( $ 0 $ 代表醒， $ 1 $ 代表睡)，则：
如果我们直接转移的话，初始状态的睡或不睡会影响后面的转移（环形），所以分类讨论：
- 当初始状态为醒的时候（正常转移）：
其中
\[f[0][0][0] = 0 \]- 当初始状态为睡的时候（此时要将初始休息的时间算上）：
其中
\[f[1][1][1] = a[1]; \]最后将两个答案合并起来即可；
可以发现，对于环形的分类讨论，状态转移方程基本一样，但初始化会有差异；
另外，此题有空间的限制，需要把 $ f $ 数组的第一维用滚动数组滚掉；
#include <iostream>
#include <cstring>
using namespace std;
int n, b;
int a[10000005];
int f[2][3831][2]; //0醒, 1睡;
int f1[2][3831][2];
int main() {
cin >> n >> b;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(f, 0xcf, sizeof(f));
memset(f1, 0xcf, sizeof(f1));
f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= b; j++) {
if (j > i) continue;
f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
f[i & 1][j][1] = max(f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + a[i]);
if (j == 0) f[i & 1][j][1] = 0xcfcfcfcf;
}
}
f1[1][1][1] = a[1];
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= b; j++) {
if (j > i) continue;
f1[i & 1][j][0] = max(f1[(i - 1) & 1][j][0], f1[(i - 1) & 1][j][1]);
f1[i & 1][j][1] = max(f1[(i - 1) & 1][j - 1][0], f1[(i - 1) & 1][j - 1][1] + a[i]);
if (j == 0) f1[i & 1][j][1] = 0xcfcfcfcf;
}
}
cout << max(max(f[n & 1][b][0], f[n & 1][b][1]), f1[n & 1][b][1]);
return 0;
}
二. 倍增优化
倍增优化的关键是找出一个可以随意划分的状态，最后对状态进行拼接得到答案；
所谓随意划分，即此状态可以拆分成任意多个长度为 $ 2^n $ 的子状态，且拼接时任意两个子状态不互相影响，并且最后的答案就是要求的正确答案；
为什么一个状态能够随意划分成任意多个长度为 $ 2^n $ 的子状态？
对于任意一个正整数，我们可以给他转变成一个二进制数，我们知道，一个二进制数可以表示成 $ 2 $ 的很多次方相加，所以可以；
例题
Luogu P1081 [NOIP2012 提高组] 开车旅行
本题有三个关键信息：已行驶的天数，所在城市，小A和小B各自行驶的路程长度；
若已知出发城市与天数，即可求得小A和小B各自行驶的路程长度，并且依据题意，天数还能反映谁现在在开车，所以我们可以把“天数” 作为“阶段”进行状态设计；
定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发，两人共行驶 $ i $ 天，$ k $ 先开车，最终会到达的城市；
很显然，这样开会炸内存，而天数又可以随意划分，可以考虑倍增优化；
重定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发，两人共行驶 $ 2^i $ 天，$ k $ 先开车，最终会到达的城市；
其中 $ 0 $ 代表小A先开车， $ 1 $ 代表小B先开车；
对于初始化，我们现在知道谁先开车，要求到那个城市，只需知道小A或小B在某一个城市时，下一个会到哪里即可，可以预处理出两个数组 $ ga[i] $ 和 $ gb[i] $ 分别表示小A在城市 $ i $ 时，下一个会到哪个城市和小B在城市 $ i $ 时，下一个会到哪个城市；
对于问题 $ 2 $，我们可以同时维护两个数组 $ da[i][j][k] $ 和 $ db[i][j][k] $ 分别表示从城市 $ j $ 出发，两人共行驶 $ 2^i $ 天，$ k $ 先开车，小A行驶的路程总长度以及小B行驶的路程总长度；
对于问题 $ 1 $，我们只需枚举出发点，找最小的即可；
则：
- 对于预处理
因为小A和小B只能往后走，所以我们可以从后往前遍历，并同时维护一个单调递增的序列（可以用 $ multiset $）其实应该是平衡树，但我不会，每次只需找当前节点旁边一位或两位的最小值和次小值即可（建议参考下面的代码）；
- 对于初始化
- 对于状态转移方程
- 对于 $ da $ 和 $ db $ 的初始化
对于 $ dis $ 的维护，可以在维护单调递增的序列同时顺便维护；
- 对于$ da $ 和 $ db $的状态转移方程
这里 $ i = 1 $ 时不同，因为 \(2^1\) 只能拆成两个$ 2^0 $ ，$ 2^0 = 1 $ 是奇数，开车的人不同，其它的是偶数，开车的人相同；
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int n;
int h[10000005];
int x0, m;
struct sss{
long long id, he;
bool operator <(const sss &A) const {
return he < A.he;
}
};
long long f[18][100005][2]; // 0 a, 1 b;
long long da[18][100005][2];
long long db[18][100005][2];
multiset<sss> p;
void init() {
p.insert({0, 9999999999999999});
p.insert({0, 9999999999999999});
p.insert({n + 1, -9999999999999999});
p.insert({n + 1, -9999999999999999}); //防止访问越界
for (long long i = n; i >= 1; i--) {
long long ga, gb;
p.insert({i, h[i]});
multiset<sss>::iterator q = p.lower_bound({i, h[i]});
q--;
long long lid = (*q).id, lh = (*q).he;
q++;
q++;
long long rid = (*q).id, rh = (*q).he;
q--;
if (abs(rh - h[i]) >= abs(lh - h[i])) {
gb = lid;
q--; q--;
if (abs(rh - h[i]) < abs((*q).he - h[i])) {
ga = rid;
} else {
ga = (*q).id;
}
} else {
gb = rid;
q++; q++;
if (abs((*q).he - h[i]) < abs(lh - h[i])) {
ga = (*q).id;
} else {
ga = lid;
}
}
f[0][i][0] = ga;
f[0][i][1] = gb;
da[0][i][0] = abs(h[ga] - h[i]);
db[0][i][1] = abs(h[gb] - h[i]);
}
}
pair<long long, long long> w(long long s, long long x) {
long long p = s;
long long la = 0;
long long lb = 0;
for (int i = 17; i >= 0; i--) {
if (f[i][p][0] && la + lb + da[i][p][0] + db[i][p][0] <= x) {
la += da[i][p][0];
lb += db[i][p][0];
p = f[i][p][0];
}
}
return {la, lb};
}
int main() {
cin >> n;
for (long long i = 1; i <= n; i++) cin >> h[i];
cin >> x0;
cin >> m;
init();
long long tt = 10;
for (int i = 1; i <= 17; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= 1; k++) {
if (i == 1) {
f[i][j][k] = f[0][f[0][j][k]][1 - k];
da[i][j][k] = da[0][f[0][j][k]][1 - k] + da[0][j][k];
db[i][j][k] = db[0][f[0][j][k]][1 - k] + db[0][j][k];
} else {
f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];
db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
}
}
}
}
long double ans = 1.00 * 0x3f3f3f3f;
long long an = 0;
for (int i = 1; i <= n; i++) {
pair<long long, long long> a = w(i, x0);
long long la = a.first;
long long lb = a.second;
if (lb == 0) continue;
long double d = 1.00 * la / (1.00 * lb);
if (d < ans) {
ans = d;
an = i;
} else if (d == ans) {
if (h[an] < h[i]) an = i;
}
}
cout << an << endl;
long long a, b;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
pair<long long, long long> c = w(a, b);
cout << c.first << ' ' << c.second << endl;
}
return 0;
}
一般在设计出状态以后，发现空间复杂度不符合要求，且有状态能够随意划分，则可以使用倍增优化；
三. 数据结构优化
适用范围：
-
时间复杂度能够忍受 $ \Theta (n \ log \ n) $
-
状态转移方程中要维护 $ \max $ 或 $ \min $ 或 $ sum $ 且区间固定；
一般使用线段树或树状数组
例题
To be continued...
标签：总结,状态,int,db,long,da,优化,DP From： https://www.cnblogs.com/PeppaEvenPig/p/18242685