当前位置: 首页 > news >正文

dp 总结 1

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}\) 个相同物品那么显然会超时, 因为 \(\sum\limits_{x\in[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";

时间复杂度总结

像线性 dp 就是 \(O(n*k)\), 其中 \(k\) 为转移复杂度, 比如之后会讲的优化就能搞出 \(k=\log n\).

背包 dp 就比较固定了, 都是 \(O(n*W)\). 特别的, 由于多重背包是二进制搞来的, 所以多重背包的 \(n'=\sum\limits_{x\in[1,n]}\log x\)

下期预告

区间 dp, 状压 dp.

http://www.hskmm.com/?act=detail&tid=23223

相关文章:

  • 2025年10月3日
  • Python作用域知识梳理
  • 美化中转站
  • go mod 面试题
  • 多轮对话系统设计的逻辑陷阱与解决方案
  • 【光照】[PBR][菲涅尔]实现方法对比
  • 20251002NOIP模拟赛
  • P10279 [USACO24OPEN] The Winning Gene S题解
  • zsh
  • 从零搭建雷池WAF:环境配置、安装部署与Web防护实战
  • 论文速读记录 | 2025.10
  • 【Rust GUI开发入门】编写一个本地音乐播放器(15. 记录运行日志) - Jordan
  • 6 种常见 AI 编程协作便捷的方法总结
  • DeploySharp开源发布:让C#部署深度学习模型更加简单
  • 别样的国庆作业大战
  • ROS2之服务
  • macOS上优雅运行Docker容器
  • 题解:CF1770H Koxia, Mahiru and Winter Festival
  • HarmonyOS之LocalStorage - 详解
  • Spring Boot Logback:实现定时任务日志与业务日志隔离 - Higurashi
  • 网络流 最小割 Dinic算法
  • 15.VLANIF(2025年9月30日) - 教程
  • 树莓派搭建NAS之一:安装系统
  • 新手Markdown学习
  • 马云归来,“新零售”不死 - 指南
  • RNN
  • 10.2笔记
  • Shell / Bash 学习
  • 【Linux 架构探幽:从入门到内核・系统编程开篇】基础指令与权限精讲,筑牢框架制作根基
  • 使用 Dart 进行验证码识别