dp 总结 1

技术分享 5个月前 (10-03) 0 999+

关注

dp 总结 1

闲来无事, 把刚学明白的 dp 笔记整理一下.

shout out to professor Adzlpxsn.

基本的, 状态, 转移, 方程

状态

一句话概况即为当前的属性.

比如说, 贝贝现在是 (30) 岁, 发了 (0) 张专辑, 我们就可以说 (f_{30}=0).

这里我们说 (30) 和 (0) 是不同的信息, 所以一个状态 (f_{x}=y) 里包含的信息其实有 (x) 和 (y).

同样的, (f_{x,y}=z) 里包含的信息有 (3) 个, 即 (x) (y) (z).

转移

转移, 就是说用 (f_{x}) 推算 (f_{y}), 或者用 (f_{x}) 和 (f_{y}) 推算 (f_{z}).

举个例子.

贝贝的新专辑 "金手指", 第 (x) 首歌是 boombap 还是 trap 取决于第 (x-1) 首和第 (x-2) 首, 即 (f_{x}=(f_{x-1}+f_{x-2}) bmod 2). 那么我们就说 (f_{x}) 由 (f_{x-1}) 和 (f_{x-2}) 转移而来.

方程

方程就是把转移的过程写成人类能看懂的东西, 比如 "数学语言" "自然语言" "编程语言".

线性 dp

最简单的线性 dp, 就是跳跃问题.

problem:AtCoder-dp_a

考虑状态, 我们让 (f_{x}) 表示现在位于 (stone_{x}) 时最少跳了多少.

转移就比较容易了, (f_{x}=operatorname{std::min}(f_{x-2}+|h_{x-2}-h_{x}|,f_{x-1}+|h_{x-1}-h_{x}|)).

没什么好讲的, 注意边界条件初始化就好了, 难的题就很难.

背包 dp

这个就好玩了.

01 背包

我个人觉得背包 dp 和线性 dp 大抵是有血缘关系的罢.

problem:AtCoder-dp_d

可以想到, 我们让 (f_{c}) 表示在背包容量为 (c) 时的最大价值.

于是有转移方程 (f_{c}=operatorname{std::max}(f_{c},f_{c-w_{x}}+v_{x})).

那么这时候我们有一个问题.

如果内层循环从 (w_{x}) 枚举到 (W), 那么有可能会造成重复选择, 但题意说每个物品只有 (1) 个.

于是我们可以调转内层循环的方向, 从 (W) 枚举到 (w_{x}), 此时每个物品就只会被选一次了.

代码

for(ll	x=1;x<=n;x++)	// 枚举每个物品 	for(ll	c=W;w[x]<=c;c--)	// 枚举背包大小 		f[c]=std::max(f[c],f[c-w[x]]+v[x]);	// 转移 std::cout<<f[W]<<"n";

完全背包

再考虑, 如果每个物品可以选无数次呢?

problem:洛谷-P1616

显然, 只要把内层循环的方向调回去就可以了.

for(ll	x=1;x<=n;x++)	// 枚举每个物品 	for(ll	c=w[x];c<=W;c++)	// 枚举背包大小 		f[c]=std::max(f[c],f[c-w[x]]+v[x]);	// 转移 std::cout<<f[W]<<"n";

多重背包

现在我们说, 每个物品不止有 (1) 个, 但也不能无限选, 于是我们说物品 (x) 有 (t_{x}) 个, 这就是多重背包.

problem:洛谷-1776

如果当成 (t_{x}) 个相同物品那么显然会超时, 因为 (sumlimits_{xin[1,n]}t_{x}ge+infin).

于是我们想, 我们学计算机最重要的是什么? 是二进制.

是的, 我们只要拆分成二进制就好了.

std::vector<td>v,w; for(td	x=1;x<=n;x++){ 	td	vx,wx,tx; 	std::cin>>vx>>wx>>tx; 	for(td	f=1;f<=tx;f<<=1){	// 二进制分解 		v.emplace_back(vx*f); 		w.emplace_back(wx*f); 		tx-=f; 	}	if(tx!=0){	// 最后还剩一点点, 单独做成一个 		v.emplace_back(vx*tx); 		w.emplace_back(wx*tx); 	} }

然后跑一遍 01 背包就解决了.

分组背包

当每一组物品里只能选 (1) 个的时候应该怎么办呢?

problem:洛谷-P1757

这里留给读者思考, 简单放一下代码, 和 01 背包也差不多.

ll	t=0; std::vector<std::vector<ll>>g(n+1); for(ll	x=1;x<=n;x++){ 	ll	s; 	std::cin>>w[x]>>v[x]>>s; 	t=std::max(t,s); 	g[s].emplace_back(x); } for(ll	s=1;s<=t;s++) 	for(ll	c=W;0<=c;c--) 		for(ll	x:g[s]) 			if(w[x]<=c) 				f[c]=std::max(f[c],f[c-w[x]]+v[x]); std::cout<<f[W]<<"n";