1.https://codeforces.com/gym/103470/problem/H
题意:
在一棵树上的每个节点都有不同数量的蝴蝶。当你进入一个节点时,若那个节点上有蝴蝶,你将会抓住那个节点的蝴蝶,但你会惊动那个节点的子节点里的蝴蝶。你从一个节点到另一个节点,并抓到蝴蝶的时间为1秒,被惊动的蝴蝶将会在 t i ( t i < = 3 ) t_i(t_i<=3) ti(ti<=3)秒后飞走。
从顶点1开始,请问最多可以抓到多少蝴蝶?
题解:
将子树全部分成三种,一种是从子树根节点一直往下做,记为 f ( x ) f(x) f(x);一种是从子树的根节点已经被取走了,但是也从这个点出发一直往下做,记为 g ( x ) g(x) g(x);最后一种是进入一个根节点,但是立刻掉头回到原来的点,再走下一棵树,记为 h ( x ) h(x) h(x)。
因此,我们可以得到一下公式 f ( u ) = a u + g ( u ) , h ( u ) = a u + ∑ g ( v ) f(u)=a_u+g(u),h(u)=a_u+sum{g(v)} f(u)=au+g(u),h(u)=au+∑g(v)。
接下来考虑 g u g_u gu如何计算。
第一种情况,当我们从 u u u节点到达一个子节点 v v v之后就一直走下去,其他子节点的蝴蝶就无法抓到,那此时的状态转移方程为 g ( u ) = m a x { f ( v i ) + ∑ v j ≠ v i g ( v j ) } = m a x { a v } + ∑ g ( v ) g(u)=max{f(v_i) + sum_{v_jne v_i}{g(v_j)}}=max{a_v}+sum{g(v)} g(u)=max{f(vi)+∑vj=vig(vj)}=max{av}+∑g(v),
第二种情况,但我们从 u u u节点到达一个子节点 v v v之后就掉头,去其他子树,这样子状态转移方程为 g ( u ) = m a x { f ( v i ) + h ( v j ) + ∑ v i ≠ v j ≠ v k g ( v k ) } = m a x { a ( v i ) + h ( v j ) + ∑ v j ≠ v k g ( v k ) } g(u)=max{f(v_i)+h(v_j)+sum_{v_ine v_j ne v_k }{g(v_k)}}=max{a(v_i)+h(v_j)+sum_{v_j ne v_k }{g(v_k)}} g(u)=max{f(vi)+h(vj)+∑vi=vj=vkg(vk)}=max{a(vi)+h(vj)+∑vj=vkg(vk)}。然后这个式子如果要枚举则要 O ( n 2 ) O(n^2) O(n2)的时间复杂度,我们可以再优化,我们的 a ( v i ) a(v_i) a(vi)必然是取最大值,那么就一直取最大值,而 h ( v j ) h(v_j) h(vj)就一直枚举。当枚举到 v i = v j v_i=v_j vi=vj时,我们的 a a a取第二大值即可。也就是说,我们枚举哪个点是只走一步就掉头的点,掉头前往 t = 3 t=3 t=3的存在最多蝴蝶的点,然后再在这个点一路往下跑。
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, T;
int f[N], g[N], h[N];
int a[N], t[N];
vector<int> ma[N];
void ready()
{
IOS;
cin >> T;
}
void dfs(int u, int fa) {
int max1 = 0, max2 = 0, maxa=0;
int res = 0;
for (auto v : ma[u]) {
if (v == fa) continue;
dfs(v, u);
}
for (auto v : ma[u]) {
if (v == fa) continue;
res += g[v];
maxa = max(maxa, a[v]);
}
h[u] = a[u] + res;
g[u] = maxa + res;
for (auto v : ma[u]) {
if (v == fa || t[v] != 3) continue;
if (a[v] > max1) {
max2 = max1;
max1 = a[v];
}
else {
max2 = max(max2, a[v]);
}
}
for (auto v : ma[u]) {
if (t[v] == 3 && a[v] == max1) {
g[u] = max(g[u], max2 + h[v] + res - g[v]);
}
else {
g[u] = max(g[u], max1 + h[v] + res - g[v]);
}
}
f[u] = a[u] + g[u];
}
void work()
{
cin >> n;
ffor(i, 1, n) {
a[i] = f[i] = g[i] = h[i] = t[i] = 0;
ma[i].clear();
}
ffor(i, 1, n) cin >> a[i];
ffor(i, 1, n) cin >> t[i];
ffor(i, 1, n - 1) {
int u; int v;
cin >> u >> v;
ma[u].push_back(v);
ma[v].push_back(u);
}
dfs(1, 0);
cout << f[1] << 'n';
}
signed main()
{
ready();
while(T--)
work();
return 0;
}
总结,动态规划,不管是哪种动态规划,一定要找到状态,状态一定要包括了所有状态,然后推出状态转移方程。
最后
以上就是活泼钥匙最近收集整理的关于[树形DP] The 2021 ICPC Asia Nanjing Regional Contest H题的全部内容,更多相关[树形DP]内容请搜索靠谱客的其他文章。
发表评论 取消回复