题目

传送门= ̄ω ̄=//这题还是我贡献给LUOGU的呢!

题目描述

小 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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *