【题解】P3698 [CQOI2017]小Q的棋盘

【题解】P3698 [CQOI2017]小Q的棋盘

【题解】P3698 [CQOI2017]小Q的棋盘

题目大意

给定一棵无根树,求从根节点出发移动N步最多可经过多少节点,节点可重复经过,但不重复计数

Solution

既然是最优化问题,考虑树形DP
容易想到,设\(f[x][i][0/1]\)表示在x这棵子树上走\(i\)步,是否(\(0\)表示否,\(1\)表示是)回到根节点,最多经过节点个数
然后就是我一开始推的状态转移方程(其实是错的):

\[f[x][i][0]=max\{f[x][i][0],f[x][i-c][1]+f[y][c-1][0]\} (1<=c<=i) \]

\[f[x][i][1]=max\{f[x][i][1],f[x][i-c][1]+f[y][c-2][1]\}(2<=c<=i) \]

意思分别是:

  • 在x这棵子树上走\(i\)步,不回到根节点,最多经过节点个数\(=\)在x这棵子树的前(j-1)个儿子中走\((i-c)\)步,回到根节点,最多经过节点个数+在x第j个儿子这棵子树上走(c-1)步,不回根节点最多经过的节点个数 [(i-c)+(c-1)=(i-1),还有1步是从x走到sonx(j)]
  • 在x这棵子树上走\(i\)步,回到根节点,最多经过节点个数\(=\)在x这棵子树的前(j-1)个儿子中走\((i-c)\)步,回到根节点,最多经过节点个数+在x第j个儿子这棵子树上走(c-2)步,回到根节点,最多经过的节点个数 [(i-c)+(c-2)=(i-2),还有2步是从x走到sonx(j)再走回来]

交上去以后Wa了3个点

开始查错,发现状态转移错了

如下图

【题解】P3698 [CQOI2017]小Q的棋盘

正确答案为红线标注,为5,但我的程序输出4

错误在于这个式子漏了一种情况

\[f[x][i][0]=max\{f[x][i][0],f[x][i-c][1]+f[y][c-1][0]\} (1<=c<=i) \]

不回到根节点有两种情况;

  1. 在前(j-1)个儿子里先走回来,再在第j个儿子里走下去,不回来
  2. 在第j个儿子里走回来,再在前(j-1)个儿子里走下去,不回来

我的式子中不包含第2种

所以Right Answer:

\[f[x][i][0]=max\{f[x][i][0],f[x][i-c][1]+f[y][c-1][0],f[x][i-c][0]+f[y][c-2][1](c>=2)\} (1<=c<=i) \]

\[f[x][i][1]=max\{f[x][i][1],f[x][i-c][1]+f[y][c-2][1]\}(2<=c<=i) \]

在这道题中我还犯了一个错误,一开始没有倒序循环,具体见代码

总结

一道树上背包好题,体积为步数,价值为经过的节点数
通过这道题,明白了树上背包转移时,实际上一个状态被滚动了,其相当于背包中的前几个物品,即当前节点的前几个儿子

Code

#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<int>s[105];
inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();	}
	return x*w;
}
const int M=1e6+10;
int v,n,f[105][105][2];
void dfs(int x,int fa)
{
	for(int i=0;i<=n;++i) f[x][i][1]=f[x][i][0]=1;
	for(int i=0;i<s[x].size();++i)
	{
		int y=s[x][i];
		if(y==fa) continue;
		dfs(y,x);
		for(int j=n;j;--j)//倒序循环,原因类似01背包,否则儿子j这颗子树会被重复选
		  for(int c=1;c<=j;++c)
		    {
		    	f[x][j][0]=max(f[x][j][0],f[x][j-c][1]+max(f[y][c-1][0],f[y][c-1][1]));
		    	if(c>=2) f[x][j][0]=max(f[x][j][0],f[x][j-c][0]+f[y][c-2][1]);
			}
		for(int j=n;j;--j)//同上
		  for(int c=2;c<=j;++c)
		    {
		    	f[x][j][1]=max(f[x][j][1],f[y][c-2][1]+f[x][j-c][1]);
//		    	f[x][j][1]=max(f[x][j][1],f[x][j-c][1]+f[y][c-2][1]);
			}	
	}
}
int main()
{
    v=read();n=read();
    int a,b;
	for(int i=1;i<v;++i){
    	a=read();b=read();
    	s[a].push_back(b);
    	s[b].push_back(a);
	}
	dfs(0,-1);
	cout<<max(f[0][n][0],f[0][n][1])<<endl;
	return 0;
}
/*
5 5
1 0
1 2
1 3
2 4
*/
上一篇:[CQOI2017] 小Q的棋盘


下一篇:[CQOI2017]老C的方块