4813: [Cqoi2017]小Q的棋盘
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 804 Solved: 441
[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<VOutput
输出一行一个整数，表示最多经过的格点数量。Sample Input
5 2
1 0
2 1
3 2
4 3Sample Output
3
从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。HINT
Source
普及题？数据范围这么小？
f[i][j]表示以i为根的子树走j步最多能走几个点（不要求返回i节点），g[i][j]要求返回，直接递推即可。
考虑贪心，首先一棵子树能走完肯定会尽量走完，因为除了最后一步的那条链之外每个点走的步数都为2（因为要返回）。
直接枚举最后在哪里停下，设停下的深度为$d[x]$（根节点深度为0），则答案为$d[x]+1+\frac{m-d[x]}{2}=\frac{d[x]+m+2}{2}$
DP:
#include<iostream>
#include<cstdio>
#include<cstring>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=;
int u,v,f[N][N],g[N][N],cnt,n,m,ans,to[N<<],nxt[N<<],h[N];
char ch;
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs(int x,int fa){
f[x][]=g[x][]=;
for (int i=h[x],k; i; i=nxt[i])
if ((k=to[i])!=fa){
dfs(k,x);
for (int j=m; j; j--)
for (int l=; l<j; l++){
if (l<j-) f[x][j]=max(f[x][j],f[k][l]+f[x][j-l-]),
g[x][j]=max(g[x][j],f[k][l]+g[x][j-l-]);
g[x][j]=max(g[x][j],g[k][l]+f[x][j-l-]);
}
}
} int main(){
freopen("chessboard.in","r",stdin);
freopen("chessboard.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,n-) scanf("%d%d",&u,&v),add(u+,v+),add(v+,u+);
dfs(,);
rep(i,,m) ans=max(ans,g[][i]);
printf("%d\n",ans);
return ;
}
贪心：
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std; const int N=;
int n,m,u,v,ans,to[N<<],nxt[N<<],h[N],cnt,dep[N];
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs(int x,int fa){
if (dep[x]>m) return;
ans=max(ans,(dep[x]+m+)>>);
for (int i=h[x],k; i; i=nxt[i]) if ((k=to[i])!=fa) dep[k]=dep[x]+,dfs(k,x);
} int main(){
freopen("chessboard.in","r",stdin);
freopen("chessboard.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,n) scanf("%d%d",&u,&v),u++,v++,add(u,v),add(v,u);
dfs(,); printf("%d\n",min(ans,n));
return ;
}