洛谷P3698 [CQOI2017]小Q的棋盘 题解

题目链接：P3698 [CQOI2017]小Q的棋盘

题意：

小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 $V$ 个格点，编号为$0,1,2,\dots , V−1$，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小 Q 现在想知道，当棋子从格点 $0$ 出发，移动 $N$ 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

对于 $100\%$ 的测试点，$N,V \le 100,~0 \le a_i,b_i< V$ 。

显然树上背包

值得注意的是，我们并不知道走的路线有没有回到 $u$

因此要多加一维

设 $f_{u,j,0/1}$ 表示 $u$ 所在子树，走了 $j$ 步，$0/1$ 表示是/否回到 $u$

不难发现

$$f_{u,j,0}=\max_{v \in \text{son}(u)}\left\{f_{u,j,0},f_{u,j-k,0}+f_{v,k-2,0}\right\} \\f_{u,j,1}=\max_{v \in \text{son}(u)}\left\{f_{u,j,1},f_{u,j-k,1}+f_{v,k-2,0},f_{u,j-k,0}+f_{v,k-1,1}\right\}$$

注意一下边界问题就好了

时间复杂度 $O(nm^2)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(115)

struct Edge{int u,v,next;}e[N<<1];
int n,m,pos=1,f[N][N][2],head[N];
#define Max(a,b) a=max(a,b)
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int fa)
{
    f[u][0][0]=f[u][0][1]=1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
        for(int j=m; j>=0; j--)
        {
            Max(f[u][j][1],f[u][j-1][0]+f[v][0][1]);
            for(int k=2; k<=j; k++)
            {
                Max(f[u][j][0],f[u][j-k][0]+f[v][k-2][0]);
                Max(f[u][j][1],max(f[u][j-k][1]+f[v][k-2][0],f[u][j-k][0]+f[v][k-1][1]));
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,0xc0,sizeof(f));
    cin >> n >> m;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u+1,v+1);
        addEdge(v+1,u+1);
    }
    dfs(1,1);
    int res=0;
    for(int i=0; i<=m; i++)
        res=max(res,f[1][i][1]);
    cout << res << '\n';
    return 0;
}

upd.20220722

模拟赛考原题写挂了，顺便发现一个问题

虽然老师数据挂了我才挂的，但是还是发现了这个问题

为什么答案要用

int res=0;
for(int i=0; i<=m; i++)
    res=max(res,f[1][i][1]);
cout << res << '\n';

而不用

cout << g[1][m] << '\n';

从 $m$ 的角度看，多走肯定不会减少答案

但是如果 $m > 2(n-1)$ ，那么按照正常的dp是走不出这样的步数的

所以可以用前者输出答案，或者读入后加一句

m=min(m,2*n-2);

然后其实memset没什么必要，具体看下面代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(115)

int n,m,pos=1,head[N],f[N][N],g[N][N];
struct Edge{int u,v,next;}e[N<<1];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int fa)
{
    f[u][0]=g[u][0]=1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v; if(v==fa) continue;
        dfs(v,u);
        for(int j=m; j>=1; j--)
            for(int k=0; k<j; k++)
            {
                g[u][j]=max(g[u][j],f[u][j-k-1]+g[v][k]);
                if(j-k-2>=0)
                {
                    f[u][j]=max(f[u][j],f[u][j-k-2]+f[v][k]);
                    g[u][j]=max(g[u][j],g[u][j-k-2]+f[v][k]);
                }
            }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    // memset(f,0xc0,sizeof(f));
    // memset(g,0xc0,sizeof(g));

    cin >> n >> m; m=min(m,2*n-2);
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u+1,v+1); addEdge(v+1,u+1);
    }
    dfs(1,1);
    cout << g[1][m] << '\n';
    // int res=0;
    // for(int i=0; i<=m; i++)
    //     res=max(res,g[1][i]);
    // cout << res << '\n';
    return 0;
}