bzoj 4813: [Cqoi2017]小Q的棋盘

2023-02-26 14:48:10

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

树型DP。。。

设f[i][j]表示从i点出发走j步不走会i点的最多的点数。。

设dp[i][j]表示从i点出发走j步并且回到i的最多的点数。。

f[x][j]可以有三种转移：

1.f[x][j]=dp[x][j-k-1]+dp[y][k]

2.f[x][j]=dp[x][j-k-1]+f[y][k]

3.f[x][j]=dp[y][k]+f[x][j-k-2](这个有点小坑。。。)

然后dp[x][j]就是一种转移

然后直接大力树型背包。。。注意枚举到K,不然会WA。。。

// MADE BY QT666

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=3000;

int head[N],to[N],nxt[N],cnt;

int f[N][N],dp[N][N],n,K,size[N];

void lnk(int x,int y){

  to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;

  to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;

}

void dfs(int x,int fa){

  size[x]=1;dp[x][0]=1;

  for(int i=head[x];i;i=nxt[i]){

    int y=to[i];if(y==fa) continue;

    dfs(y,x);size[x]+=size[y];

    for(int j=K;j>=0;j--){

      for(int k=0;k<=j;k++){

	if(j-k>=1) f[x][j]=max(f[x][j],dp[x][j-k-1]+dp[y][k]);

	if(j-k>=1) f[x][j]=max(f[x][j],dp[x][j-k-1]+f[y][k]);

	if(j-k>=2) f[x][j]=max(f[x][j],dp[y][k]+f[x][j-k-2]);

	if(j-k>=2) dp[x][j]=max(dp[x][j],dp[x][j-k-2]+dp[y][k]);

      }

    }

  }

  for(int i=1;i<=K;i++) f[x][i]=max(f[x][i],f[x][i-1]),dp[x][i]=max(dp[x][i],dp[x][i-1]);

}

int main(){

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  scanf("%d%d",&n,&K);int x,y;

  for(int i=1;i<n;i++) scanf("%d%d",&x,&y),lnk(x+1,y+1);

  dfs(1,0);printf("%d\n",max(f[1][K],dp[1][K]));

  return 0;

}

码农公寓