[BZOJ4813][CQOI2017]小Q的棋盘(DP,贪心)

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<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
[Submit][Status][Discuss]

普及题？数据范围这么小？

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:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=110;
 9 int u,v,f[N][N],g[N][N],cnt,n,m,ans,to[N<<1],nxt[N<<1],h[N];
10 char ch;
11 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
12 
13 void dfs(int x,int fa){
14     f[x][0]=g[x][0]=1;
15     for (int i=h[x],k; i; i=nxt[i])
16         if ((k=to[i])!=fa){
17             dfs(k,x);
18             for (int j=m; j; j--)
19                 for (int l=0; l<j; l++){
20                     if (l<j-1) f[x][j]=max(f[x][j],f[k][l]+f[x][j-l-2]),
21                                   g[x][j]=max(g[x][j],f[k][l]+g[x][j-l-2]);
22                     g[x][j]=max(g[x][j],g[k][l]+f[x][j-l-1]);
23                 }
24         }
25 }
26 
27 int main(){
28     freopen("chessboard.in","r",stdin);
29     freopen("chessboard.out","w",stdout);
30     scanf("%d%d",&n,&m);
31     rep(i,1,n-1) scanf("%d%d",&u,&v),add(u+1,v+1),add(v+1,u+1);
32     dfs(1,0);
33     rep(i,0,m) ans=max(ans,g[1][i]);
34     printf("%d
",ans);
35     return 0;
36 }

贪心：

#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std;

const int N=107;
int n,m,u,v,ans,to[N<<1],nxt[N<<1],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+2)>>1);
    for (int i=h[x],k; i; i=nxt[i]) if ((k=to[i])!=fa) dep[k]=dep[x]+1,dfs(k,x);
}

int main(){
    freopen("chessboard.in","r",stdin);
    freopen("chessboard.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,2,n) scanf("%d%d",&u,&v),u++,v++,add(u,v),add(v,u);
    dfs(1,0); printf("%d
",min(ans,n));
    return 0;
}