讨论/技术交流/分享 | 树形背包复杂度/
分享 | 树形背包复杂度
  • 问题1:给定大小为n(n1000)n(n\le 1000)的二叉树,每个点有价值wiw_i.对所有k=1,2,,nk=1,2,\cdots,n,求包含根的大小为kk的连通块的最大价值.

  • 问题2:给定n(n300)n(n\le 300),初始时有n×nn\times n的正方形格子,每次需要移除其中一个给定的格子,共n2n^2次,问剩下格子能组成长方形的数量.
    解释:如果n=2n=2,一开始有441×11\times1,222×12\times1,221×21\times2,112×22\times2,共9个长方形,移除掉其中任意一个后会剩下331×11\times1,112×12\times1,111×21\times2,共5个长方形.(来源:2020 ICPC EC Final B)

问题1

先看问题1,很容易写出动态规划方程:
记在uu的子树中包含uu的大小为kk的连通块的最大价值为dp[u][k]dp[u][k],那么有:
{dp[u][0]=0,dp[u][k]=maxx+y=k1{dp[Lu][x]+dp[Ru][y]}+wu,\begin{cases} dp[u][0]=0,\\ dp[u][k]=\max\limits_{x+y=k-1}\{dp[L_u][x]+dp[R_u][y]\}+w_u, \end{cases}
其中LuL_uRuR_u表示uu的左右结点.

分析这个算法的复杂度,可以发现共有O(n2)O(n^2)的状态,每个状态的计算需要O(n)O(n)的时间,因此时间复杂度是O(n3)O(n^3).那么这是不是紧的上界呢?答案是否定的.

考虑转移的计算,本质上对每个结点而言,需要转移的次数是左子树和右子树大小的乘积,如果看成左子树中的每个点和右子树中的每个点组成的点对会对复杂度有O(1)O(1)的贡献,可以发现每个点对只会在最近公共祖先处有贡献,因此总复杂度实际上是O(n2)O(n^2)的.

问题2

问题2需要一点点计数的知识,首先需要知道初始长方形的数量,实际上就是(n(n+1)2)2(\dfrac{n(n+1)}{2})^2,因为每个长方形本质上是行和列各选一个区间组合而成,而长度为nn的格子区间数量有n(n+1)2\dfrac{n(n+1)}{2}个.

然后对这个问题最自然的想法就是按顺序对每个格子,求包含这个格子的长方形数量,然后去掉这个格子.为了方便计数,需要保存up[i][j]up[i][j]down[i][j]down[i][j],表示(i,j)(i,j)向上/向下还剩的连续格子数,每次去掉一个格子,只需要O(n)O(n)重新计算数组中这列上的值,这部分的复杂度是O(n3)O(n^3)的.

然后要去掉每个格子时,分别枚举包含这个格子的长方形的左边界和右边界,并且在枚举的过程中记录上边界和下边界的取值范围(up和down数组最小值),然后对每个给定的左边界和右边界,包含这个格子的长方形的数量就是上边界方案数×\times下边界方案数.这样对每个格子计算的复杂度是O(n2)O(n^2),那么总的复杂度就是O(n4)O(n^4).在赛后就有人声称数据过水,暴力O(n4)O(n^4)也可以通过此题.实际上,这样做的复杂度是O(n3)O(n^3)的.

重新对每行考虑这个过程:如果按移除的顺序对每行建树,即移除掉一个格子后,将它作为根,左右还剩的格子分别作为它的左右子树(如果你知道什么是笛卡尔树,其实就是按移除时间大小建笛卡尔树),那么这个复杂度就是左子树乘右子树的复杂度.因此每总复杂度是O(n2)O(n^2),总复杂度就是O(n3)O(n^3)的.

这两个看似是暴力的算法实际上都可以轻松通过所设定的时限.很多时候,看起来像是错误的复杂度其实是正确的,因此不妨在比赛中尝试提交暴力代码.

思考题

问题1去掉二叉树的限制(即每个结点可以有任意多子结点),那么复杂度是多少?

3
共 2 个回复

这个树形DP的复杂度我之前也给人讲过几次,感觉知道的人不太多的样子... 再补充一个结论,如果是对所有k=1,,Kk=1,\dots,K求的话,可以做到O(nK)O(nK)
话说这个EC Final B,应该有比O(n3)O(n^3)更快的做法吧?

1

何神

1