没有合适的资源?快使用搜索试试~ 我知道了~
首页图论dp实践:暴力与滚动数组解分层图问题
本文档是一篇关于图论和动态规划的教程,针对的是IT学习者,特别是编程新手。作者以“蒟蒻の图论刷题(更新中)Ⅰ - 树/图dp”为名,分享了自己在处理一些比赛题目中的经验,这些题目主要来自中国青少年在线创新竞赛(如TJOI和ZJOI)。其中,重点讨论了一个名为“可乐”的问题,这是一道涉及到分层图和矩阵优化的题目。 题目中提到的问题涉及到了状态转移的动态规划方法。选手需要考虑每座城市的三个状态:0代表上一时刻已经在该城市,1表示当前时刻刚到达,2则表示自爆。核心思路是通过维护一个滚动数组,记录每个时刻0状态(即已到达)和1状态(即新到达)的城市总数,以及2状态(自爆)的累计数量。通过这种方式,可以简化计算,避免遍历整个时间线,从而节省时间和空间。 作者提到使用暴力法和滚动数组(也就是常数级别的额外空间)解决了这个问题,这展示了即使面对复杂问题,简单而巧妙的算法设计也能解决问题,同时表达了对于O2(可能是某种优化技术或数据结构)的赞美。 代码部分展示了如何初始化动态规划数组dp,以及如何根据输入数据进行状态转移。通过递推公式,更新dp数组,最终计算出答案。这里的代码片段使用了C++语言,并定义了一些常用宏和常量,如向量g用于存储图的邻接关系,N定义了一个较大的整数,dp数组用于保存状态转移的结果,以及mod用于取模操作。 这篇文档不仅提供了实际问题的解决策略,还包含了解题技巧和代码实现,对于想要提升图论和动态规划技能的IT学习者来说,是非常有价值的参考资料。
资源详情
资源推荐
蒟蒻の图论刷题蒟蒻の图论刷题(更新中更新中)Ⅰ 树树/图图dp
总算来补自己好久前买下的坑了,题目内容均来自洛谷题单
目录目录[TJOI2017]可乐[ZJOI2006]物流运输[HNOI/AHOI2018]道路[ZJOI2007]时态同步[TJOI2017]城市
[TJOI2017]可乐可乐
tag上是分层图+矩阵优化,但是被我用暴力+滚动数组水过去了(赞美O2!)对每个点有三种状态,0:上一秒已经在这个城
市了;1:这一秒刚到;2:自爆。只需要记录最后时刻0、1的和以及所有时刻2的和即可,注意滚动数组的更新。
#include
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define mod 2017
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 40
vector g[40];
const int N = 1e6+5;
int dp[maxn][3][2];int n,m,t;
//0 原地 1 移动 2爆炸
int main(){
IOS
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dp[1][0][0]=1;
cin>>t;
int cnt=1;
ll ans=0;
for (int i = 1; i <=t ; ++i) {
for (int j = 1; j <=n ; ++j) {
int tmp=((cnt-1)%2+2)%2;
dp[j][0][cnt]=(dp[j][0][tmp]+dp[j][1][tmp])%mod;
dp[j][2][cnt]=(dp[j][1][tmp]+dp[j][0][tmp])%mod;
for(auto k:g[j]){
dp[k][1][cnt]+=(dp[j][1][tmp]+dp[j][0][tmp])%mod;
}
dp[j][1][tmp]=0;
ans=(ans+dp[j][2][cnt])%mod;
}
cnt++;
cnt%=2;
}
cnt=((cnt-1)%2+2)%2;
for (int l = 1; l <=n ; ++l) {
ans=(ans+dp[l][0][cnt]+dp[l][1][cnt])%mod;
}
cout<<ans;
return 0;
}
[ZJOI2006]物流运输物流运输
这种数据范围当然直接暴力啦
(又是写乱前向星的日常,debug了半天发现是前向星的锅)
一道不错的最短路+dp的题,先记录每个码头不能运输的日子,然后用dp[i][j]记录i到j天的最短路,然后就是从1开始枚举+区间
分割了。
#include
#define ll long long
#define fi first
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define mod 2017
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 25
#define int long long
下载后可阅读完整内容,剩余4页未读,立即下载
weixin_38611796
- 粉丝: 8
- 资源: 943
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++多态实现机制详解:虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统:无向图实现最短路径探索
- SQL2005彻底删除指南:避免重装失败
- GTD时间管理法:提升效率与组织生活的关键
- Python进制转换全攻略:从10进制到16进制
- 商丘物流业区位优势探究:发展战略与机遇
- C语言实训:简单计算器程序设计
- Oracle SQL命令大全:用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解:电路与程序设计
- 反激开关电源设计:UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程:创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功