动态规划课程树型dp例题
string
http://www.nowcoder.com/questionTerminal/ea1026bf23af48a99445158235efd5e5
小G有一个大树
题目链接
求树的重心
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 2000; char buf[100000],*p1=buf,*p2=buf; inline char nc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int w = 1, data = 0; char ch = 0; while(ch != '-' && (ch < '0' || ch > '9')) ch = nc(); if(ch == '-') w = -1, ch = nc(); while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc(); return w * data; } struct Edge { int to, next, w; }edge[MAXN<<1]; int cnt, head[MAXN]; void add(int u, int v, int w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void add_edge(int u, int v, int w = 0) { add(u, v, w); add(v, u, w); } int n, siz[MAXN], root, temp = Inf; void dfs(int x, int pre) { siz[x] = 1; int mx = 0; for(int i = head[x]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; dfs(v, x); siz[x] += siz[v]; mx = max(mx, siz[v]); } mx = max(mx, n - siz[x]); if(mx < temp) { temp = mx; root = x; } } int main() { n = read(); memset(head, -1, sizeof head); for(int i = 1; i < n; i++) { int u = read(), v = read(); add_edge(u, v); } dfs(1, -1); printf("%d %d", root, temp); return 0; }
Rinne Loves Edges
设 为以u为结点的子树,删最少多少边权可以使得所有叶子结点不到达根
对于一个节点的每一个分叉,一定会有一条边被转移,分出一个叉就代表一个至少一个子节点,那么对于每一颗子树,要么取其子树的结果,要么断掉和子树的边,取最小值转移即可
题目链接
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 1e5+10; char buf[100000],*p1=buf,*p2=buf; inline char nc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline ll read(){ ll w = 1, data = 0; char ch = 0; while(ch != '-' && (ch < '0' || ch > '9')) ch = nc(); if(ch == '-') w = -1, ch = nc(); while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc(); return w * data; } struct Edge { int to, next; ll w; }edge[MAXN<<1]; int cnt, head[MAXN], du[MAXN]; void add(int u, int v, ll w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; du[u]++; } void add_edge(int u, int v, ll w = 0) { add(u, v, w); add(v, u, w); } int n, m, s; ll dp[MAXN]; void dfs(int u, int pre) { if(du[u] == 1 && u != s) { dp[u] = Linf; return; } for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; dfs(v, u); dp[u] += min(dp[v], edge[i].w); } } int main() { n = read(); m = read(); s = read(); memset(head, -1, sizeof head); for(int i = 1; i <= m; i++) { int u = read(), v = read(), w = read(); add_edge(u, v, w); } dfs(s, -1); printf("%lld", dp[s]); return 0; }
Cell Phone Network
题目链接
每个点可以覆盖其相邻点,要求在树上选最少的点,使得整棵树被覆盖
考虑以 为根的子树,
被覆盖有三种情况
本身就被选择
的儿子被选择
的父亲被选择
发现 的父亲对x也产生了影响,那么可以把父亲也设进x的状态,则dp的几个状态分别为
自己被选择
的儿子被选择
的父亲被选择
那么考虑状态转移
自己被选择时,其子节点选或者不选可以,且子节点不选的时候可以是其父节点
被选,那么转移方程则为
- x的子树被选时,只需要其一个儿子被选就可以,那么对于其子树的两种选择1,2,先使
,若
的儿子统计的状态中有1状态,即
的儿子本身被选择了,则
就可以算被覆盖,若
的所有儿子全部选择了2状态即
的所有儿子本身没有被选择,而是
的儿子
再下一层的儿子被选择了,间接的把
选择了,这种情况,需要在
的众多儿子中挑一个被选择,那么挑的这个儿子就是从被其儿子覆盖,变成其本身被选择,改变量最小的,统计一下就可以了
的父亲被选择的时候,那么其儿子可以被选择也可以不被选择,转移则为
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 1e4+10; char buf[100000],*p1=buf,*p2=buf; inline char nc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int w = 1, data = 0; char ch = 0; while(ch != '-' && (ch < '0' || ch > '9')) ch = nc(); if(ch == '-') w = -1, ch = nc(); while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc(); return w * data; } struct Edge { int to, next, w; }edge[MAXN<<1]; int cnt, head[MAXN]; void add(int u, int v, int w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void add_edge(int u, int v, int w = 0) { add(u, v, w); add(v, u, w); } int dp[MAXN][12], n; //0 i 自己 //1 i 儿子 //2 i 父亲 void dfs(int u, int pre) { dp[u][0] = 1; int pos = Inf; dp[u][13] = 0; dp[u][14] = 0; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; dfs(v, u); dp[u][0] += min(dp[v][0], min(dp[v][15], dp[v][16])); dp[u][17] += min(dp[v][0], dp[v][18]); dp[u][19] += min(dp[v][0], dp[v][20]); pos = min(pos, dp[v][0] - min(dp[v][0], dp[v][21])); } dp[u][22] += pos; } int main() { n = read(); memset(head, -1, sizeof head); memset(dp, 0x3f, sizeof dp); for(int i = 1; i < n; i++) { int u = read(), v = read(); add_edge(u, v); } dfs(1, 0); printf("%d", min(dp[1][0], dp[1][23])); return 0; }
二叉苹果树
题目链接
因为题目要求的是保留 条边最多的权值,那么就相当于选择
条边使得这些边的路径可以到根节点1,把边权下放到点权,则相当于选
个点,这些点连起来可以和根联通,这样的话若想选择点
,则必须先选择
的父节点
,问题转换成了树形背包
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 500; char buf[100000],*p1=buf,*p2=buf; inline char nc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int w = 1, data = 0; char ch = 0; while(ch != '-' && (ch < '0' || ch > '9')) ch = nc(); if(ch == '-') w = -1, ch = nc(); while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc(); return w * data; } struct Edge { int to, next, w; }edge[MAXN<<1]; int cnt, head[MAXN]; void add(int u, int v, int w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void add_edge(int u, int v, int w = 0) { add(u, v, w); add(v, u, w); } int n, q, val[MAXN], dp[MAXN][MAXN]; void dfs1(int u, int pre) { for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; val[v] = edge[i].w; dfs1(v, u); for(int j = q+1; j >= 0; j--) for(int k = j; k >= 0; k--) if(j - k >= 0) dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]); } for(int i = q+1; i >= 1; i--) dp[u][i] = dp[u][i-1] + val[u]; } int main() { n = read(); q = read(); memset(head, -1, sizeof head); for(int i = 1; i < n; i++) { int u = read(), v = read(), w = read(); add_edge(u, v, w); } dfs1(1, -1); cout << dp[1][q+1]; return 0; }
没有上司的舞会
设状态 为不选择
时权值最大最多是,
为选择
时权值最大为多少
- 当选择
的时候,其儿子全部不能选择,那么转移方程则为
- 当不选择
的时候,其儿子可以选择也可以不选择,那么转移方程为
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 2e4; struct Edge { int to, next, w; }edge[MAXN<<1]; int cnt, head[MAXN]; void add(int u, int v, int w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void add_edge(int u, int v, int w = 0) { add(u, v, w); add(v, u, w); } int n, dp[MAXN][2], r[MAXN], du[MAXN], ans; void dfs(int u) { dp[u][1] = r[u]; int mx1 = 0, mx0 = 0; for(int i = head[u]; i != - 1; i = edge[i].next) { int v = edge[i].to; dfs(v); mx1 += dp[v][0]; mx0 += max(dp[v][0], dp[v][1]); } dp[u][1] = r[u] + mx1; dp[u][0] = mx0; ans = max(ans, max(dp[u][1], dp[u][0])); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(head, -1, sizeof head); cin >> n; for(int i = 1; i <= n; i++) cin >> r[i]; for(int i = 1; i < n; i++) { int l, k; cin >> l >> k; add(k, l); du[l]++; } int root; for(int i = 1; i <= n; i++) { if(du[i] == 0) root = i; } dfs(root); cout << ans; return 0; }
Strategic game
题目要求选择最少的点,覆盖所有的边,对于点 ,若选择
,则其儿子结点可以选也可以不选,若不选
结点,则其儿子结点必须全部都选,转移方程为
- 选
结点:
- 不选
结点:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 2000; int n; struct Edge { int to, next, w; }edge[MAXN<<1]; int cnt, head[MAXN]; void add(int u, int v, int w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void add_edge(int u, int v, int w = 0) { add(u, v, w); add(v, u, w); } void init() { cnt = 0; memset(head, -1, sizeof head); } int vis[MAXN], dp[MAXN][2]; void dfs(int u, int pre) { vis[u] = 1; dp[u][1] = 1; dp[u][0] = 0; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; dfs(v, u); dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][1], dp[v][0]); } } void doit() { init(); for(int i = 1; i <= n; i++) { char s[100]; scanf("%s", s); int x = 0, m = 0, top = 0; while(s[top] != ':') x = x*10 + s[top++]-'0'; top += 2; while(s[top] != ')') m = m*10 + s[top++]-'0'; for(int j = 1; j <= m; j++) { int v; scanf("%d", &v); add_edge(x, v); } } memset(dp, 0x3f, sizeof dp); memset(vis, 0, sizeof vis); int ans = 0; for(int i = 0; i < n; i++) { if(!vis[i]) dfs(i, -1), ans += min(dp[i][0], dp[i][1]); } cout << ans << endl; } int main() { while(scanf("%d", &n) != EOF) doit(); return 0; }
树上子链
对于每个结点 来说,其最最长链肯定为它的最长子链和次长子链之和,统计一下就可以了,本题需要注意的是,因为点权可以为负数,那么有可能出现只选一个点的情况,答案记录的时候初始值要为
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 1e5+10; char buf[100000],*p1=buf,*p2=buf; inline char nc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int w = 1, data = 0; char ch = 0; while(ch != '-' && (ch < '0' || ch > '9')) ch = nc(); if(ch == '-') w = -1, ch = nc(); while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc(); return w * data; } struct Edge { int to, next, w; }edge[MAXN<<1]; int cnt, head[MAXN]; void add(int u, int v, int w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void add_edge(int u, int v, int w = 0) { add(u, v, w); add(v, u, w); } int n, val[MAXN]; ll dp[MAXN], ans = -Linf; void dfs(int u, int pre) { dp[u] = 0; ans = max(ans, 1ll* val[u]); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == pre) continue; dfs(v, u); ans = max(ans, dp[u] + dp[v] + 1ll*val[u]); dp[u] = max(dp[v], dp[u]); } dp[u] += val[u]; } int main() { n = read(); memset(head, -1, sizeof head); for(int i = 1; i <= n; i++) val[i] = read(); for(int i = 1; i < n; i++) { int u = read(), v = read(); add_edge(u, v); } dfs(1, -1); cout << ans; return 0; }
吉吉王国
没开 调了一个小时......
实际上就是 Rinne Loves Edges 这道题的一个变形,要求删去的最长长度最小,那么二分这个长度 ,设
为以
点为根的子树的最小花费,所以边长大于
的边全部不删,直接转移子树的答案,若边长小于等于
则这条边可以删也可以不删,比较下删这条边还是这个子树的代价,取更小的。
二分答案求解
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef unsigned long long ull; #define lsiz(x) int(x.size()) #define lch rt<<1 #define rch rt<<1|1 const ll Linf = 0x7f7f7f7f7f7f7f7f; const int Inf = 0x3f3f3f3f; const int MAXN = 1e6+10; char buf[100000],*p1=buf,*p2=buf; inline char nc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline ll read(){ ll w = 1, data = 0; char ch = 0; while(ch != '-' && (ch < '0' || ch > '9')) ch = nc(); if(ch == '-') w = -1, ch = nc(); while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc(); return w * data; } ll n, m; struct Edge { ll to, next, w; }edge[MAXN<<1]; ll cnt, head[MAXN], du[MAXN]; void add(ll u, ll v, ll w = 0) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; du[u]++; } void add_edge(ll u, ll v, ll w = 0) { add(u, v, w); add(v, u, w); } ll dp[MAXN]; void dfs(ll u, ll pre, ll lim) { if(du[u] == 1 && u != 1) { dp[u] = Inf; return; } dp[u] = 0; for(ll i = head[u]; i != -1; i = edge[i].next) { ll v = edge[i].to; if(v == pre) continue; dfs(v, u, lim); if(edge[i].w > lim) dp[u] += dp[v]; else dp[u] += min(dp[v], edge[i].w); } } bool check(ll lim) { dfs(1, -1, lim); return dp[1] <= m; } int main() { memset(head, -1, sizeof head); n = read(); m = read(); for(ll i = 1; i < n; i++) { ll u = read(), v = read(), w = read(); add_edge(u, v, w); } ll l = 0, r = 2000, ans = -1; while(l <= r) { ll mid = (l + r) >> 1; if(check(mid)) r = mid - 1, ans = mid; else l = mid + 1; } cout << ans; return 0; }