首页 > 其他分享 >[DP] DP优化总结

[DP] DP优化总结

时间:2024-06-11 21:57:42浏览次数:3  
标签:总结 状态 int db long da 优化 DP

写在前面

$ DP $,是每个信息学竞赛选手所必会的算法,而 $ DP $ 中状态的转移又显得尤为关键。本文主要从状态的设计和转移入手,利用各种方法对朴素 $ DP $ 的时间复杂度和空间复杂度进行优化与处理,以达到满足题目要求的目的;

参考文献:
动态规划算法的优化技巧 毛子青
c++ DP总结
《算法竞赛进阶指南》

一. 环形与后效性处理

我们都知道,一个题能用 $ DP $ 来解,需要满足以下两个性质:

  1. 无后效性
  2. 最优子结构

但对于有些题目,如果要用 $ DP $ 解决的话,会出现环形与后效性的问题;

所谓环形与后效性,即状态的转移与 $ DP $ 的方向并不完全一致;

举个例子,状态的转移可以从左到右,也可以从右到左,但 $ DP $ 的方向只能为从左到右从右到左,此时称此 $ DP $ 为有后效性;

当状态初能够由状态末转移而来(此时构成了一个环形)时,此时称此 $ DP $ 为环形;

对于前者的处理,我们通常会改变 $ DP $ 的遍历方向,使其能够与状态转移的方向一致,当无法一致时,可以使用迭代的方法取得最优解;

对于后者,我们通常对初始状态分类讨论,找出几种不是环形的 $ DP $,破环成链,分别处理,最后取最优解;

例题

后效性

Luogu CF24D Broken robot

本题的高斯消元解法不再叙述,考虑 $ 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;
}

环形

Luogu P6064 Naptime G

设计状态 $ f[i][j][k] $ 表示在每 $ N $ 个小时的前 $ i $ 个小时中,休息 $ j $ 个小时,且第 $ j $ 个小时的状态( $ 0 $ 代表醒, $ 1 $ 代表睡),则:

如果我们直接转移的话,初始状态的睡或不睡会影响后面的转移(环形),所以分类讨论:

  1. 当初始状态为醒的时候(正常转移):

\[ f[i][j][0] = \max(f[i - 1][j][0], f[i - 1][j][1]) \]

\[ f[i][j][1] = \max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + a[i]) \ (j \neq 0) \]

其中

\[f[0][0][0] = 0 \]

  1. 当初始状态为睡的时候(此时要将初始休息的时间算上):

\[f[i][j][0] = \max(f[i - 1][j][0], f[i - 1][j][1]) \]

\[f[i][j][1] = \max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + a[i]) \ (j \neq 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 $,我们只需枚举出发点,找最小的即可;

则:

  1. 对于预处理

因为小A和小B只能往后走,所以我们可以从后往前遍历,并同时维护一个单调递增的序列(可以用 $ multiset $)其实应该是平衡树,但我不会,每次只需找当前节点旁边一位或两位的最小值和次小值即可(建议参考下面的代码);

  1. 对于初始化

\[f[0][j][0] = ga[j] \]

\[f[0][j][1] = gb[j] \]

  1. 对于状态转移方程

\[f[1][j][k] = f[0][f[0][j][k]][1 - k] \]

\[f[i][j][k] = f[i - 1][f[i - 1][j][k]][k] \ (i \neq 1) \]

  1. 对于 $ da $ 和 $ db $ 的初始化

\[da[0][j][0] = dis[j][ga[j]] \]

\[da[0][j][1] = 0 \]

\[db[0][j][0] = 0 \]

\[db[0][j][1] = dis[j][gb[j]] \]

对于 $ dis $ 的维护,可以在维护单调递增的序列同时顺便维护;

  1. 对于$ da $ 和 $ db $的状态转移方程

\[da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k] \ (i = 1) \]

\[da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k] \ (i > 1) \]

\[db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k] \ (i = 1) \]

\[db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k] \ (i > 1) \]

这里 $ 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;
}

一般在设计出状态以后,发现空间复杂度不符合要求,且有状态能够随意划分,则可以使用倍增优化;

三. 数据结构优化

适用范围:

  1. 时间复杂度能够忍受 $ \Theta (n \ log \ n) $

  2. 状态转移方程中要维护 $ \max $ 或 $ \min $ 或 $ sum $ 且区间固定;

一般使用线段树或树状数组

例题

To be continued...

标签:总结,状态,int,db,long,da,优化,DP
From: https://www.cnblogs.com/PeppaEvenPig/p/18242685

相关文章

  • C / C++ 保留两位小数(setprecision(n)的一些用法总结)
    转载:https://blog.csdn.net/qq_36667170/article/details/79265224做题遇到保留两位小数的题目,课本上写的又多又杂,网上查来的也是一堆内容需要筛选,눈_눈还是自己总结一下吧。首先说C++代码 #include<iomanip>//不要忘了头文件 //第一种写法 cout<<setiosflags(io......
  • [DP] [倍增优化] Luogu P1081 [NOIP2012 提高组] 开车旅行
    [NOIP2012提高组]开车旅行题目描述小\(\text{A}\)和小\(\text{B}\)决定利用假期外出旅行,他们将想去的城市从$1$到\(n\)编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市\(i\)的海拔高度为\(h_i\),城市\(i\)和城市\(j\)之间的距......
  • DP(优化)
    史不分好坏。是史就应该冲进......
  • atcoder 官方dp题单题解(持续更新)
    题单链接:https://atcoder.jp/contests/dp/tasks洛谷搜索:https://www.luogu.com.cn/problem/list?keyword=at_dp&type=AT|B|CF|P|SP|UVA&page=1A题目链接:https://atcoder.jp/contests/dp/tasks/dp_a简单线性dp.dp[i]表示在i这个位置的最小代价,转移的时候把两种选择都考虑......
  • 需求响应|动态冰蓄冷系统与需求响应策略的优化研究(Matlab代码实现)
        ......
  • 基于多时段动态电价的电动汽车有序充电策略优化(Matlab代码实现)
    ......
  • 【课程总结】Day7:深度学习概述
    前言本篇文章,我们将通过示例来逐步学习理解导数、求函数最小值、深度学习的本质、以及使用numpy和pytorch实操深度学习训练过程。线性回归线性回归内容回顾在《【课程总结】Day5(下):PCA降维、SVD分解、聚类算法和集成学习》中,我们已经了解到线性回归以及线性回归可以表......
  • 持续总结中!2024年面试必问 20 道分布式、微服务面试题(九)
    上一篇地址:持续总结中!2024年面试必问20道分布式、微服务面试题(八)-CSDN博客十七、什么是配置管理在微服务架构中的重要性?在微服务架构中,配置管理是确保系统灵活性、可维护性和可扩展性的关键组成部分。以下是配置管理在微服务架构中的重要性:1. 环境一致性:微服务架构通常......
  • 苹果WWDC超全总结:GPT-4o加入iOS 18 | 最新快讯
    如果不是本届WWDC24(苹果全球开发者大会)最后阶段,苹果重新定义了AI,用「AppleIntelligence」取代「ArtificialIntelligence」,那么这场苹果年度盛会的高光时刻将会变成「iPad终于有了计算器应用」这种愚人节玩笑水平的更新。但好在,苹果玩的「谐音梗」,经得起推敲和琢磨......
  • leetcode刷题-归纳总结
    框架思维124.求⼆叉树中最⼤路径和后序遍历最大路径转换为为求单边最大路径105.根据前序和中序遍历构造二叉树前序遍历,找到根节点构建root,得到左右子树区间,左右子树递归构建注意:1.终止条件2.构建unordered_map230.寻找⼆叉搜索树中的第k⼩的元素⼆叉搜索树即左支树所有......