动态规划 树形DP
P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
如果上司来那他的下属就不回来，若上司不来，下属可以来也可以不来；上司和下属的关系和树类似，所以我们可以设一个dp[i][j]，dp[i][1]表示这个人参加，那么他只能有dp[i的子树][0]转移过来，dp[i][0]表示这个人不参加，那么它可以由dp[i的子树][1]或dp[i的子树][0]转移过来，所以dp方程就有了，，，
dp[i][1]+=dp[i的子树][0];
dp[i][0]+=max(dp[i的子树][0],dp[i的子树][1]);
#include
#define ll long long
#define lowbit(x) ((-x)&(x))
using namespace std;
const int mod=1000000007;
const ll inf=0x3f3f3f3f;
const ll bou=1e15;
const int maxn=1e7+5;
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res*=a;a*=a;b>>=1;}return res;
}
ll n,a[10005],dp[10005][2],vis[10005];
vectorv[10005];
void dfs(ll u){for(int i=0;i Strategic game - POJ 1463 - Virtual Judge (vjudge.net)
这个题其实和没有上司的舞会挺像的，dp[i][0]代表没放士兵，没放的话那与i相连的节点就必须要放了，dp[i][1]代表放了士兵，那么与它相连的就可以不放了，最后统计出来就可以了；
#include
#include
#include
#include
#include
#include
#include Cell Phone Network - POJ 3659 - Virtual Judge (vjudge.net)
第i个点选了之后会覆盖到i的子节点和i的父亲， 和上一个题不一样，上一个题只会影响到子节点，是边覆盖，这题是点覆盖；影响到父亲那两个状态就不能表示了
dp[i][0]表示选了这个i点子节点全部覆盖所需要的最少信号塔
dp[i][1]表示不选i点，但是i点被子节点覆盖掉，i的子节点全部覆盖需要的最少信号塔
dp[i][2]表示不选i点而且也没有被子节点覆盖，i的子节点全部覆盖需要的最少信号塔
dp[i][0]选了这个点了，那么他的子节点是什么状态都无所谓了所以是
dp[i][0]+=min(dp[j][0],dp[j][1],dp[j][2]);
dp[i][2]不选i点且没被子节点覆盖，那么他只能有dp[j][1]转移过来，所以
dp[i][2]+=dp[j][1];
dp[i][1]不选i点且被子节点覆盖了，那么我们至少要选一个dp[j][0],如果存在dp[j][0]<=dp[j][1]那样的话一定是选dp[j][0],如果不存在的话，那我们就要选一个损失最少的dp[j][0]来转移；
【动态规划】树形DP完全详解！ - RioTian (cnblogs.com)
#include
#include
#include
#include
#include
#include
#include P2014 [CTSC1997] 选课 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一门课和他的先修课可以看成是子节点与父结点的关系，也包括那个0号节点，将0号节点看成是所有没有先修课的先修课，也就是根节点，dp[u][j]表示以u这个节点为根，选m门课可获得的最大学分，所以先去dfs u的每个子节点，之后枚举j从m~1（01背包），然后再枚举一层k从0~j-1或从j-1~k都行，因为要算上根节点，所以k<=j-1，表示以该子节点为根选了多少课，之后枚举一下，最后输出dp[0][m+1]就可以了，因为算上0号节点总共可以选m+1门课；
题解 P2014 【选课】 - HullEssien 的博客 - 洛谷博客
#include
#include
#include
#include
#include
#include
#include 二叉苹果树 - LibreOJ 10153 - Virtual Judge (vjudge.net)
这题也是一个树上背包的问题，dp[u][j]表示u这个节点留了j根树枝所能获得的最大的苹果树，
0<=j<=q,设s为他的子树，要想s转移到u，s留了k根树枝，那就有
dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[s][k]+v[u][s].ap),因为u到v之间是有一根树枝的，所以是j-k-1，ap是u到v树枝的苹果树，这个问题也可以扩展到n叉树上，代码应该和这个类似，都是背包的思想
(6条消息) 【基础算法】二叉苹果树_Pi_UK(wjh)的博客-CSDN博客
#include
#include
#include
#include
#include
#include
#include P1273 有线电视网 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
不知道为什么看到是树上背包的问题就有点不敢写，但是思路还算是比较简单的，dp[u][j]代表以u为根选了j个子节点所能得到的最大收益，转移的时候就是按照背包的转移方式来就可以，但是自己却没有写出来，，，下一个一定要自己写一下啊！！！
题解 P1273 【有线电视网】 - yqw2486 的博客 - 洛谷博客
#include
#include
#include
#include
#include
#include
#include P3478 [POI2008] STA-Station - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二次扫描加换根dp，二次扫描在这里就是先dfs遍历一次求出每个点的子树包括自己一共有多少个节点，和以1为根的深度之和，也可以换成别的节点，只是作为一个dfs的起始点而已；第二次扫描就是求出以每个点为根能得到的深度和，这个深度和的求解就用到了换根dp，假设u本来是根节点，他的子节点v要作为新的根，那么显然深度和会有变化，每个节点的深度也有变化，对于v和v的子树来讲，他们的深度其实是都要减1，因为根节点从u变为v,路径减少了一层，所以一共减少了s[v]，另外对于不是v或v的子树的，他们的路径终点从u变为v，路径增加了一层，所以再加上
n-s[v] ,所以最后的方程就是dp[v]=dp[u]-s[v]+n-s[v]--->dp[v]=dp[u]+n-2*s[v];
最后再遍历一遍求出深度和最大的节点就可以了；
P3478 [POI2008] STA-Station - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include
#include
#include
#include
#include
#include
#include P2986 [USACO10MAR] Great Cow Gathering G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
和上一个树的深度和类似，此时需要多几个变量，c[i]就是每个牛棚的牛数，vector里存一个pair代表u到v所走的路长度，dep[u]代表能到该点的牛一共产生的不方便值，siz[u]代表的是u和u的子树一共有多少牛，与上一题不同的地方就在于dep[u]要放在循环里面并且写法稍微不一样了，比如遍历到j这个子节点了，是要去dfs(j)求出siz[j]，然后再去乘以j,u两点的距离才是j的牛到u所产生的不方便值，并且u不止j这一个子节点，所以要在循环内；
另外就是换根dp的方程了，思路是一样的，从u换到子节点v，那么v和v的子节点所拥有的牛就都要减去v到u的这段距离，而其他节点的牛要都加上v到u的这段距离；
#include
#include
#include
#include
#include
#include
#include Rinne Loves Edges (nowcoder.com)
把图往树那边想，题目可以转化为删除哪些边权可以使得s这个点到不了任何叶子节点，考虑一下，我们可以直接以s为根来思考问题，想一下我们可以在s的儿子j上就切断，也可以在j的儿子上切断，决定条件就是要切断边权最小的，那我们设dp[u]表示以u为根所有叶子节点都到不了u所需要的代价，那么方程就是dp[u]+=min(dp[j],dis[u][j]);要么在u和u的儿子j切断，要么就让j和j的儿子去重复这个抉择，最后得到的dp[s]就是答案；
【动态规划】树形DP完全详解！ - RioTian (cnblogs.com)
#include
#include
#include
#include
#include
#include
#include 吉吉王国 (nowcoder.com)
这个题和上一个题类似，dp的部分都是一样的，只不过添加了条件，只要和二分搭配使用就可以了，但我卡在了奇怪的点上，明明代码是差不多的，但一个过一个没过，离谱
#include
#define ll long long
using namespace std;
const ll inf=0x3f3f3f3f;
ll n,m,dp[1005];
struct node{ll to,w;
};
vectorv[1005];
void dfs(ll u,ll fa,ll lim){bool f=0;for(int i=0;i>1;if(check(mid)){r=mid-1,ans=min(ans,mid);flag=1;}else l=mid+1;}if(flag) printf("%lld\n",ans);else printf("-1\n");return 0;
}
哦~我明白了，我的代码是这样的
#include
#define ll long long
using namespace std;
const ll inf=0x3f3f3f3f;
ll n,m,dp[1005];
struct node{ll to,w;
};
vectorv[1005];
void dfs(ll u,ll fa,ll lim){if(v[u].size()>1) dp[u]=0;
//if(v[u].size()>1||u==1) dp[u]=0;cout<>1;if(check(mid)){r=mid-1,ans=min(ans,mid);flag=1;}else l=mid+1;}if(flag) printf("%lld\n",ans);else printf("-1\n");return 0;
}
但如果是这样一组数据的话
2 9821
1 2 723
那么我的dp[1]也会是inf，不会是0，因为他们的v[u].size()都是1，所以我这个是错误的，换成下面注释的那句话就能过啦！这波是自己坑了自己俩小时
P1922 女仆咖啡厅桌游吧 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个树形dp感觉挺奇怪的，因为我都不知道如何去设计状态，看了题解之后感性的理解了一下，我们考虑一个节点u，假设他的子节点(除了自己和叶子节点)都满足了cafe==table了，那么 我们只需要将dp[u]+=dp[v]就可以了，因为加起来之后还是cafe=table，至于根节点，我们就让u和这些根节点对半分就可以了，最后再加上这个sum/2；
题解 P1922 【女仆咖啡厅桌游吧】 - 即使前路永夜 - 洛谷博客
#include
#define ll long long
using namespace std;
ll n,dp[100005];
vectorv[100005];
void dfs(ll u,ll fa){ll sum=1;for(int i=0;i 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！