题目
题目描述
小 Q 正在设计一种棋类游戏。
在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点，编号为 0,1,2 … , V− 1，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。
小 Q 现在想知道，当棋子从格点 0 出发，移动 N 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。
输入输出格式
输入格式：
第一行包含 2 个正整数 V, N，其中 V 表示格点总数，N 表示移动步数。
接下来 V − 1 行，每行两个数，表示编号为的两个格点之间有连线。
输出格式：
输出一行一个整数，表示最多经过的格点数量。
输入输出样例
输入样例 #1：
5 2
1 0
2 1
3 2
4 3
输出样例 #1：
3
输入样例 #2：
9 5
0 1
0 2
2 6
4 2
8 1
1 3
3 7
3 5
输出样例 #2：
5
说明
【输入输出样例 1 说明】
从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。
【输入输出样例 2 说明】
一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7，经过 0, 1, 3, 5, 7 这 5 个格点。
【数据规模与约定】
对于 100% 的测试点，N,V ≤ 100, 0 ≤a_i,b_i< V
题解
//我的第一个树型 dp？（可能以前打过树型 dp 然而我并不知道那是树型 dp）
很明显是棵树！
暴力不能过！
所以树型 dp（然而很奇怪，贪心可以 AC！那俩位打贪心の神犇说可以证明，然而我不会！）。
首先我们得知道这个东西：
对于一个节点，我们选中一个它的儿子节点。对于这种选法，我们有三种走的方法：
1. 向儿子节点的方向一条路走到黑，不返回到当前节点。
2. 向儿子节点的方向走一圈回来。
3. 向儿子节点的方向走一圈回来且再向另一个方向一条路走到黑，不会来。
简要地说就是：
1. ↙
2. ⟲
3. ⟲↘
走法 1 和 2 不会返回到当前节点，当然也就没法回到当前节点的父亲节点。
所以我们分两个数组存状态：
$f0[i][j]$表示当前到了节点 $i$，还可以走 $j$步时不需要回到节点 $i$时最多可以访问的节点数。
$f1[i][j]$表示当前到了节点 $i$，还可以走 $j$步时需要回到节点 $i$时最多可以访问的节点数。
具体：
对于 $dfs(u)$，我们枚举子节点为 i，再从 n（最多可以走的步数）到 1 枚举当前剩余步数为 j，再从 1 到 j 枚举下一步的剩余步数 k。
对于走法1，需要满足 $j-k>0$，然后：$f[0][u][j]=max(f[0][u][j],f[0][i][k]+f[1][u][j-k-1])$
对于走法2，需要满足 $j-k>=2$，然后：$f[1][u][j]=max(f[1][u][j],f[1][i][k]+f[1][u][j-k-2])$
对于走法3，需要满足 $j-k>=2$，然后：$f[0][u][j]=max(f[0][u][j],f[1][*i][k]+f[0][u][j-k-2])$
为什么走法 1 和走法 2 要加一个 $f[1][u][j-k-1]$或 $f[1][u][j-k-2]$呢？
因为我们可以先从别的地方绕一圈回来，再执行走法 1、走法 2。
还有，枚举 j 的时候一定要从大到小，原因就像 01 背包，要从大的到小的更新，不然状态之间会互相影响，然后 wa（考试的时候脑子抽了就写错了这里，掉了 50 分）。
其他具体看代码吧！
#include <bits/stdc++.h>
using namespace std;
template<typename tp>void in(tp & dig)
{
char c=getchar();dig=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int v,n,f[2][105][105],fa[105];
list<int> g[105];
void initdfs(int u)
{
for(list<int>::iterator i=g[u].begin();i!=g[u].end();i++)
if(*i!=fa[u])
fa[*i]=u,initdfs(*i);
}
void dfs(int u)
{
f[0][u][0]=f[1][u][0]=1;
for(list<int>::iterator i=g[u].begin();i!=g[u].end();i++)
if(*i!=fa[u])
{
dfs(*i);
for(int j=n;j>0;j--)
for(int k=0;k<j;k++)
{
if(j-k>=2)
{
f[1][u][j]=max(f[1][u][j],f[1][*i][k]+f[1][u][j-k-2]);
f[0][u][j]=max(f[0][u][j],f[1][*i][k]+f[0][u][j-k-2]);
}
f[0][u][j]=max(f[0][u][j],f[0][*i][k]+f[1][u][j-k-1]);
}
}
for(int i=1;i<=n;i++)
f[0][u][i]=max(f[0][u][i],f[0][u][i-1]),
f[1][u][i]=max(f[1][u][i],f[1][u][i-1]);
}
int main()
{
in(v),in(n);
for(int i=1,a,b;i<v;i++)in(a),in(b),g[a].push_back(b),g[b].push_back(a);
initdfs(0),dfs(0),printf("%d\n",f[0][0][n]);
return 0;
}
0 条评论