标签: 树形dp - CheaSim Blog
发表更新acm几秒读完 (大约102个字)

[77c Beavermuncher-0xFF树形dp+贪心

C. Beavermuncher-0xFF

题意

给你一颗树，树上的每个节点有$n$个海狸。现在你在节点$root$上你前往下一个节点的条件是下一个节点上面至少有一个海狸，之后你到这个节点之后，你就会吃掉这个海狸。问最多能吃掉多少只海狸。

题解

贪心+树形dp

ac代码

发表更新acm1 分钟读完 (大约182个字)

树形dp5题连做

树形dp，3天搞定

A - Information Disturbing

题意

对于一棵树，切断一些边使得每一个叶节点都无法连接到根节点，有两个要求

  • 每条边带权重，切掉的边权重和不大于$m$
  • 切掉的每条边都不能大于一个$ans$

问$ans$最小是多少？

题解

二分+树形dp

+1 ans初始化-1

看别人代码发现了个好东西，链式前项星判断节点是否为叶节点可以这样判断

1
2
3
4
if(G[head[u]].to == father) 
    该节点是叶节点 //在双向边的时候适用
if(head[u]==-1)
    该节点是叶节点 //在单向边的时候适用

ac代码

发表更新acm3 分钟读完 (大约523个字)

[hdoj4616] Game

Game

题意

给一颗树，已知每个点有权值和陷阱，你不能往回走，如果走过$c$个陷阱或者无路可走就结束，可以从任一点开始走，问能获得多少权值。

题解

树形dp。

$dp[i][j][0/1]$是在以$i$为终点，经过$j$个陷阱，$1$代表起点有陷阱，$0$代表起点没有陷阱。
转移方程

  • $dp[u][j][0]=max(dp[u][j][0],dp[v][j][0]+val[v])$
  • $dp[u][j][1]=max(dp[u][j][1],dp[v][j][1]+val[v])$ 其中$j>0$因为起点有陷阱。

答案就是枚举每个根节点中子树进入和出去，特判一下链的组成

  • 起点为trap和起点不为trap组成，路线是从trap出发到另一个起点。
  • 起点都不是trap，那么这时候就要求$j_1+j_2<c$，因为路线走到一半就可能到了trap为$c$卡主，不能走了。
  • 两个起点都为trap,那么无所谓只需要$j_1+j_2 \leq c$就可以了。

心路历程：我一开始想的是二维dp转移方程，但是只能对一个根节点求值，因为子节点也有可能走根节点那条路径，没有想到树形dp对于求解问题这么灵活，答案不一定一定是dp数组中的元素，而可以是通过拼接数组中元素来构成答案。而且我想法是从根节点走到叶子节点，而不是从子树节点出发到根节点，还是too young啊。之后我拼接了自己的垃圾二维dp，发现因为在迷宫中你碰到$c$个陷阱之后就不能走了，但是我这个二维数组不能转移方程。我两条链拼接的时候会多加几个节点，因为左右两个链如果加起来为$c$之后，其中一条链到了trap点，就不能再走了。所以才要三维数组。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
struct node{
    int next,to;
}G[maxn<<1];
int head[maxn],trap[maxn],val[maxn],dp[maxn][4][2];
int cnt,T,n,c,ans;
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    memset(head,-1,sizeof(int)*(n+2));
    memset(trap,0,sizeof(int)*(n+2));
    memset(dp,0,sizeof(dp));
    ans = 0;
}
void dfs1(int u,int fa){
    dp[u][trap[u]][trap[u]] = val[u];
    for(int i=head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(fa == v) continue;
        dfs1(v,u);
        for(int j=0;j<=c;j++){
            for(int k=0;k+j<=c;k++){
                ans = max(ans,dp[u][j][1]+dp[v][k][1]);
                if(j) ans = max(ans,dp[u][j][1]+dp[v][k][0]);
                if(k) ans = max(ans,dp[u][j][0]+dp[v][k][1]);
                if(j+k<c) ans = max(ans,dp[u][j][0]+dp[v][k][0]);
            }
        }
        for(int j=0;j+trap[u]<=c;j++){
            dp[u][j+trap[u]][0] = max(dp[u][j+trap[u]][0],dp[v][j][0]+val[u]);
            if(j) dp[u][j+trap[u]][1] = max(dp[u][j+trap[u]][1],dp[v][j][1]+val[u]);
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&c);
        init();
        rep(i,0,n) scanf("%d%d",&val[i],&trap[i]);
        rep(i,0,n-1){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        dfs1(0,-1);
        printf("%d\n",ans);
    }
    return 0;
}
发表更新acm5 分钟读完 (大约715个字)

[hdoj4661] Message Passing

HDOJ 4661: Message Passing

题意

每个人拥有一个信息，也可以传给另外一个人他拥有的所有信息。现在给定一个联络树，问至少多少次传递可以让所有人拥有所有信息。

题解

可以看出至少要$(n-1)*2$次传递，因为每个人都至少传出一次，传入一次。而怎么可以最少传递呢？我们可以假设根为中心，先将所有信息传递给他，之后再从他传递回来。这里有一点很巧妙，传入和传出的可能种类是一样的，所以我们只需要计算一次传入，平方后便是该点为中心的方案数。

因为子节点必须先传给父节点信息以免漏传，所以传入的方案数是满足一种拓扑排序的。那么可以看我之前的一篇博客，计算拓扑排序对一个点进行计算的。

那么怎么从已知的父节点的$f(root)$传递到子节点$f(v)$呢？

$s(i)$表示以$i$为根节点的子节点数目。

我们假设子节点$s(v)=q$，那么如果子节点变成根节点后，子节点的$s(v)=n$，而原来的父节点$f(u)$变成了$n-q$个子节点数目了。于是通过公式

$f(root)=(f(root)-1)!/s(1)/s(2)/…/s(n)$

我们可以推导出$f(v) = f(u) * s(q)/s(n-q)$

搞定!

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e6 + 10;
const ll mod = 1e9 + 7;
struct node{
    int to,next;
}G[maxn<<1];
int head[maxn],pre[maxn],q[maxn],vis[maxn];
ll f[maxn],sz[maxn],fac[maxn];
int cnt,n,T;
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    rep(i,0,n+1){
        head[i] = -1;
        q[i] = 0;
        f[i] = 1;
        vis[i] = 0;
        sz[i] = 0;
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&T);
    fac[0] = 1;
    rep(i,1,maxn){
        fac[i] = fac[i-1]*i % mod;
    }
    while(T--){
        scanf("%d",&n);
        init();
        rep(i,0,n-1){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        int l = 0,r = 0;vis[1] = 1;q[0] = 1;
        while(l<=r){
            int u = q[l++];
            for(int i = head[u];~i;i=G[i].next){
                int v = G[i].to;
                if(vis[v]) continue;
                pre[v] = u;
                vis[v] = 1;
                q[++r] = v;
            }
        }
        per(i,1,n){
            sz[q[i]] ++;
            sz[pre[q[i]]] += sz[q[i]];
        }
        sz[1] ++;
        ll cnt = fac[n];
        rep(i,1,n+1) cnt = (cnt*pow3(sz[i],mod-2))%mod;
        ll ans = 0;
        ans = cnt*cnt %mod;f[1] = cnt;
        rep(i,1,n){
            ll cur = f[pre[q[i]]];
            cur = cur*sz[q[i]] %mod;
            cur = cur*pow3(n-sz[q[i]],mod-2)%mod;
            f[q[i]] = cur;
            ans = (ans + cur*cur%mod) % mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
发表更新acm5 分钟读完 (大约752个字)

[UVA11174] Stand in a line

Stand in a line

题意

给定$n-1​$组关系，节点$a​$不能站在节点$b​$的前面，使得$n​$站成一行，问有多少种站法。

题解

树形dp + 组合数学

  1. 先建树，把没有父亲的节点都并入$0$节点，这样我们就有一颗完整的树了。
  2. 寻找规律，假设$f[i]$为以$i$为根节点的方案数，那么当每增加一颗子树的时候，他的组合是相当于有一个有拓扑排序方案和另外一个拓扑排序方案相组合。

我们可以这样想像，假设拓扑排序是不存在的，这些点的排序忽略，那么点可以看做是同样颜色的点，那么$x_1,x_2$个数的点排列的排列数为$(x_1+x_2)! /(x_1! * x_2!)$。而这些点其实是不一样的，他们有自身的拓扑排序顺序，于是答案就是$f(x_1) f(x_2) (x_1+x_2)!/(x1! * x_2!)$。

  1. 于是乎，我们先处理好每个节点的子节点(包含他自身)，可以用拓扑排序直接做，不用递归，当然也可以递归，于是就是相当于从子树开始处理，把所有子树的节点数的阶乘除掉就可以了。

简单写一下从递推到通向。$c_i$表示是$root$的子节点，$s(i)$表示$i$节点的子节点数。

$f(root) = f(c1)f(c2)…f(c_k)*((s(root)-1)!/s(c_1)!/s(c_2)!/…/s(c_k)!)$

$f(c_1)=f(x_1)f(x_2)…f(x_z)*((s(c_1)-1)!/s(x_1)!/s(x_2)!/…/s(x_z)!)$

$s(c_1)和s(c_1-1)$可以约掉。而且到叶子节点$f(x_1)$都变成$1$了$s(x_1)$也变成了0.

$f(root)=(s(root)-1)!/s(1)/s(2)/…/s(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4 + 10;
const ll mod = 1e9 + 7;
int T,n,m,cnt;
struct node{
    int to,next;
}G[maxn<<1];
int head[maxn],vis[maxn],sz[maxn],q[maxn],pre[maxn];
ll fac[maxn],f[maxn];
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    rep(i,0,n+1){
        vis[i] = 0;
        head[i] = -1;
        sz[i] = 0;
        pre[i] = 0;
        f[i] = 1;
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a % mod;
        b>>=1;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&T);
    fac[0] = 1;
    rep(i,1,maxn){
        fac[i] = fac[i-1]*i%mod;
    }
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,0,m){
            int u,v;scanf("%d%d",&v,&u);
            add(u,v);vis[v] = 1;
        }
        rep(i,1,n+1) if(!vis[i]) add(0,i);
        memset(vis,0,sizeof(vis));
        vis[0] = 1;
        int l=0,r=0; q[0] = 0;vis[0] = 1;
        while(l<=r){
            int u = q[l++];
            for(int i = head[u];~i;i=G[i].next){
                int v = G[i].to;
                if(vis[v]) continue;
                pre[v] = u;
                vis[u] = 1;
                q[++r] = v;
            }
        }
        per(i,1,n+1){
            sz[q[i]]++;
            sz[pre[q[i]]] += sz[q[i]];
        }
        sz[0]++;
        ll res = 0;
        ll cnt = fac[n];
        rep(i,1,n+1) cnt = cnt*pow3(sz[i],mod-2)%mod;
        printf("%lld\n",cnt);
    }
    return 0;
}

Reference:https://blog.csdn.net/xiao_k666/article/details/78609562

关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×