bzoj 4813 [Cqoi2017]小Q的棋盘

4813: [Cqoi2017]小Q的棋盘

Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 5  Solved: 1[Submit][Status][Discuss]

Description

小Q正在设计一种棋类游戏。在小Q设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能 在有连线的格点之间移动。整个棋盘上共有V个格点，编号为0,1,2…,V-1，它们是连通的，也就是说棋子从任意格 点出发，总能到达所有的格点。小Q在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。 小Q现在想知道，当棋子从格点0出发，移动N步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

 

Input

第一行包含2个正整数V,N，其中V表示格点总数，N表示移动步数。 接下来V-1行，每行两个数Ai,Bi,表示编号为Ai,Bi的两个格点之间有连线。 V,N≤ 100, 0 ≤Ai,Bi<V 

 

Output

输出一行一个整数，表示最多经过的格点数量。

 

Sample Input

5 2 1 0 2 1 3 2 4 3

Sample Output

3 从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。

HINT

 

Source

--------------------------

http://www.cnblogs.com/rwy233/p/6689641.html

树形dp

f[i][j]表示在i这棵子树里走j步且最后要回到i最多能经过的节点数

g[i][j]则表示最后不用回到i

直接dfs每做完一个子树后转移一下就可以了

代码:

#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define CH c=getchar() #define For(i,x,y) for(int i=x;i<=y;++i) using namespace std; inline int read(){ bool f=0;char CH;for(;!isdigit(c);CH)if(c=='-')f=1; int x=0;for(;isdigit(c);CH) x=(x<<1)+(x<<3)+c-48;return f?-x:x; } const int N = 1e2+5; int f[N][N],g[N][N]; int n,m; int nxt[N<<1],to[N<<1],head[N],cnt; void add(int u,int v){ nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v; nxt[++cnt]=head[v];head[v]=cnt;to[cnt]=u; } void dfs(int u,int fat){ f[u][0]=g[u][0]=1; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(v==fat) continue; dfs(v,u); for(int i=m;~i;--i){ for(int j=0;j<=i-1;++j){ if(i-j-2>=0)f[u][i]=max(f[u][i],f[v][j]+f[u][i-j-2]); g[u][i]=max(g[u][i],g[v][j]+f[u][i-j-1]); if(i-j-2>=0)g[u][i]=max(g[u][i],f[v][j]+g[u][i-j-2]); } } } for(int i=0;i<m;++i) f[u][i+1]=max(f[u][i],f[u][i+1]); for(int i=0;i<m;++i) g[u][i+1]=max(g[u][i],g[u][i+1]); } int main(){ // freopen("code.in","r",stdin); // freopen("code.out","w",stdout); n=read();m=read(); For(i,2,n){ int u=read(),v=read(); add(u,v); } dfs(0,0); printf("%d",g[0][m]); return 0; }

转载于:https://www.cnblogs.com/rwy233/p/6689641.html