dp学习(二)
树和图上的dp。
4. 简单树形dp
这些是最为简单的树形dp。
一般来说,树形dp是通过子树的dp值推出当前点的dp值。
在这里,我们默认当前节点为u,它的儿子节点为v,树的根为rt。
例题4.1 luoguP1122 最大子树和
状态转移方程:\(dp[u]=a[u]+\sum\max\{0,dp[v]\}\)
然后dfs就行了。答案为\(\max\{dp[u]\}\)
代码:
void dfs(int u)
{
vis[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int p=e[i].to;
if(!vis[p])
{
dfs(p);
dp[u]+=max(0,dp[p]);
}
}
dp[u]+=a[u];
vis[u]=0;
}
例题4.2 luoguP1352 没有上司的舞会
树上最大权独立集问题。首先我们找到根rt。
这次要分两种情况讨论,这里用\(dp[u][0/1]\)表示当前节点是选还是不选。
我们有状态转移方程:
\(dp[u][0]=\sum\max\{dp[v][0],dp[v][1]\}\)
\(dp[u][1]=a[u]+\sum dp[v][0]\)
最后答案为\(\max\{dp[rt][0],dp[rt][1]\}\)
代码:
void dfs(int u)
{
for(int i=h[u];i;i=e[i].nxt)
{
int p=e[i].to;
dfs(p);
dp[u][0]+=max(dp[p][0],dp[p][1]);
dp[u][1]+=dp[p][0];
}
dp[u][1]+=a[u];
}
5. 树上背包
可以认为是之前“有依赖的背包”的拓展。这时,物品间的依赖关系构成了一棵树。
例题5.1 luoguP2014 选课
例题5.2 luoguP1273 有线电视网
6. 二次扫描法(换根dp)
例题6.1 luoguP3478 STA-Station
例题6.2 luoguP3647 连珠线
接下来讨论图上的dp。
7. DAG上的dp
最为简单的一种,先拓扑排序,再按照拓扑序dp。
例题7 luoguP3183 食物链
当前节点的dp值就是能到达这个节点的所有节点的值相加。
一开始我们将入度为0的点的dp值赋为1,最后统计的时候记得要将单独一个点的情况(无出度)特判一下。
这里给出拓扑排序部分的代码实现,统计答案略。
void toposort()
{
queue<int> q;
for(int i=1;i<=n;i++)
if(!indeg[i])
{
q.push(i);
dp[i]=1;
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].nxt)
{
int p=e[i].to;indeg[p]--;
dp[p]+=dp[u];
if(!indeg[p])q.push(p);
}
}
}
8. 基环树上的dp
例题8.1 luoguP1453 城市环路
例题8.2 luoguP2607 骑士
例题8.3 luoguP4381 Island
9. 后效性处理
最新文章
- 应用ERP系统与企业的关系
- 注解式开发spring定时器
- sdutoj 2154 Shopping
- win7系统安装
- 开源项目:libbpg
- 最简单的jdbc程序
- Android之自定义AlertDialog无法监听控件
- jquery 元素控制(附加元素/其他内容)引进和应用
- The Swift Programming Language-官方教程精译Swift(2)基础知识
- 转:XPath路径表达式
- 五、pig学习
- centOS 6 服务管理与服务脚本
- Grafana4.2安装
- SpringBoot(一)_快速实战搭建项目
- 【easy】168. Excel Sheet Column Title 171. Excel Sheet Column Number
- Nancy 返回值详解
- 面向对象编程之OC
- Java笔记Spring(四)
- linq时间筛选以及list时间筛选
- vc++ 在程序中运行另一个程序的方法
热门文章
- 【LeetCode】904. Fruit Into Baskets 解题报告(Python)
- TensorFlow.NET机器学习入门【4】采用神经网络处理分类问题
- 第六个知识点:我们怎么把NP问题解释成一组可以在多项式内证明的命题
- MADE: Masked Autoencoder for Distribution Estimation
- Chapter 11 Why Model ?
- Vue.js高效前端开发 • 【初识Vue.js】
- Vue-cli3.0配置全局less
- 【HTML响应式项目】成人教育官网前端页面(HTML+CSS+JS实现三端适应)
- Sqoop2开启Kerberos安全模式
- 【】Apache Ranger剖析:Hadoop生态圈的安全管家