题型多而杂,我们通过学习例题的方式看一下。
T1:树的直径 考虑树形 DP。
对于每一个子树,我们都可以求出在该子树的最长路径。
对于根节点,他的所有儿子都会有一个向下的最大路径。
然后,我们维护这些路径的最大值和次大值,就可以求出经过该点且在该点里的最大路径。
T2:树的中心 直接考虑怎样求从一个点出发走到的最远距离。
对于一个点,他向下走的最大距离是很好求的,直接模仿上一题。
接下来,我们考虑向上走。
首先,走到父亲节点时,他有两种选择:继续向上走或者向下走。
向上走的部分就可以递归了,但是向下走有问题:如果向下的最大距离是经过当前点怎么办?
我们再维护一个次大值,向下的最大路径如果经过当前点的话,就给次大值。
T3:数字变换 题目传送门 LOJ
将问题抽象为一颗树的形式:假设较小的数是较大的数的父亲。
那么,每一个数,一定只有一个父亲,且一定不会形成一个环。
所以,按小到大的顺序建好树后,就可以直接求树的直径了。
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 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int N=5e4 +10 ,M=1e5 +10 ,INF=0x3f3f3f3f ;int h[N],e[M],ne[M],idx;int sum[N],d[N],ans,n;void add (int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int dfs (int x) { if (d[x]>=0 ) return d[x]; int &d1=d[x],d2=-INF; for (int i=h[x];~i;i=ne[i]) { int t=dfs (e[i])+1 ; if (t>=d1) d2=d1,d1=t; else if (t>d2) d2=t; } ans=max (ans,d1+d2); if (d1<0 ) d1=0 ; return d1; } int main () { memset (h,-1 ,sizeof h); memset (d,0xcf ,sizeof d); scanf ("%d" ,&n); for (int i=1 ;i<=n;++i) for (int j=2 ;j<=n/i;++j) sum[i*j]+=i; for (int i=1 ;i<=n;++i) if (sum[i]<i) add (sum[i],i); for (int i=1 ;i<=n;++i) if (d[i]<0 ) dfs (i); printf ("%d\n" ,ans); return 0 ; }
T4:二叉苹果树 题目传送门 LOJ
这个是一个比较简单的树形(有依赖的)背包问题。
考虑计算一个节点。
对于他的所有儿子来说,都相当于是一个分组的物品。
直接分组背包即可。
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 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int N=150 ,M=300 ;int h[N],e[M],ne[M],w[M],idx;int n,k,f[N][N];void add (int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dfs (int x,int fa) { for (int i=h[x];~i;i=ne[i]) { if (e[i]==fa) continue ; dfs (e[i],x); for (int j=k;j;--j) for (int l=0 ;l+1 <=j;++l) f[x][j]=max (f[x][j],f[x][j-l-1 ]+f[e[i]][l]+w[i]); } } int main () { memset (h,-1 ,sizeof h); scanf ("%d %d" ,&n,&k); for (int i=1 ,x,y,c;i<n;++i) { scanf ("%d %d %d" ,&x,&y,&c); add (x,y,c);add (y,x,c); } dfs (1 ,-1 ); cout<<f[1 ][k]<<endl; return 0 ; }
T5:战略游戏 题目传送门 LOJ
记录 $f[i,0]$ 为 $i$ 节点不放士兵的最小代价,$f[i,1]$ 为 $i$ 节点放士兵的最小代价。
那么,就可以得到:
就可以计算了。
(话说我尝试了一下新型的码风)
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 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int N = 1505 , M = 2 * N;int h[N], e[M], ne[M], idx;int n, f[N][2 ];bool st[N];void add (int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs (int x) { f[x][1 ] = 1 ; for (int i = h[x]; ~i; i = ne[i]) { dfs (e[i]); f[x][0 ] += f[e[i]][1 ]; f[x][1 ] += min (f[e[i]][0 ], f[e[i]][1 ]); } } int main () { memset (h, -1 , sizeof h); scanf ("%d" , &n); for (int i = 0 ; i < n; ++ i ) { int b, id, tot; scanf ("%d %d" , &id, &tot); while (tot -- ) { scanf ("%d" , &b); add (id, b); st[b] = true ; } } int rt = 0 ; while (st[rt]) rt ++ ; dfs (rt); printf ("%d\n" , min (f[rt][1 ], f[rt][0 ])); return 0 ; }
T6:皇宫看守 题目传送门 LOJ
这个题大概要使用到状态自动机模型(但是我没写)
其实也不难,就是不同的状态之间的转化。
设 $0$ 状态为儿子节点看守本节点, $1$ 状态为本节点看守,$2$ 状态为父亲节点看守。
每一个节点的三种状态,都可以通过儿子节点算出来。
具体请读者自行实现,或者看代码。
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 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int N = 1505 , M = 2 * N;int h[N], e[M], ne[M], idx;int f[N][3 ], v[N], n;bool st[N];void add (int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs (int x) { f[x][1 ] = v[x]; for (int i = h[x]; ~i; i = ne[i]) { dfs (e[i]); f[x][1 ] += min (min (f[e[i]][1 ], f[e[i]][2 ]), f[e[i]][0 ]); f[x][2 ] += min (f[e[i]][1 ], f[e[i]][0 ]); } int tot = 0 ; for (int i = h[x]; ~i; i = ne[i]) tot += min (f[e[i]][1 ], f[e[i]][0 ]); f[x][0 ] = 0x3f3f3f3f ; for (int i = h[x]; ~i; i = ne[i]) f[x][0 ] = min (f[x][0 ], tot - min (f[e[i]][1 ], f[e[i]][0 ]) + f[e[i]][1 ]); } int main () { memset (h, -1 , sizeof h); scanf ("%d" , &n); for (int i = 0 ;i < n; ++ i ) { int id, b, tot; scanf ("%d" , &id); scanf ("%d %d" , &v[id], &tot); while (tot -- ) { scanf ("%d" , &b); add (id, b); st[b] = true ; } } int rt = 1 ; while (st[rt]) rt ++ ; dfs (rt); printf ("%d\n" ,min (f[rt][0 ],f[rt][1 ])); return 0 ; }