为什么以及怎样用上下界优化保证平方复杂度

本题是典型的树上背包，正确的算法复杂度是

O(nk)

，其中

n

是树的大小，

k

是可选的物品数量。subtask1是用来卡

O(n^3)

的错误写法的（不开O2的情况下）。在我正确通过了subtask1之后，我终于想通了为啥以及如何正确地做上下界优化，特发此贴以帮助后面卡在这里的人思考。

正如很多别的复杂度分析的文章指出，只要单个子树的算法复杂度是

O(n^2)

的，那么在dp数组限制上界到

k

之后，整体算法复杂度就是

O(nk)

。这一点不再赘述。本贴核心在于怎么控制子树复杂度到

O(n^2)

。

暂且不考虑dp数组上界控制到

k

的优化。每个子树的dp数组上界开到

n_i

，即该子树大小；于是，

n=\sum_{i=1}^kn_i

。设对大小为

n

的树复杂度是

T(n)

，那么应该有

T(n)=\sum_{i=1}^kT(n_i)+M(n_1,\cdots,n_k)

，其中

M(\cdot)

是合并步的复杂度。

一种（可能）正确的写法如下。

CPP

int sz = 1;
for (const auto& [nt, w]: gr[cr]) {
	if (nt==pa) continue;
	auto [cnt, ndp] = dfs(dfs, nt, cr);
	for (int i = min(sz+cnt, k); i>=0; --i) {
		for (int j = max(0, i-min(sz, k)); j<cnt && j<=i; ++j) {
			dp[i] = max(dp[i], dp[i-j]+ndp[j]+1LL*w*(j*(k-j)+(cnt-j)*(n-cnt-k+j)));
		}
	}
}

为什么这样是对的？因为（继续忽略

k

）我们需要把循环控制在

\{(i,j):0\le i\le sz+cnt,\max\{0,i-sz\}\le j\le \min\{cnt,i\}\}

内，这是一个平行四边形（请自行画图），所以总的大小是

(1+sz)(1+cnt)\le(1+n_i)(1+\sum_{j=1}^{i-1}n_j)

。适当牺牲严谨性但便于表达，扔掉括号里的

1

，这样只会扩大后面大O里的系数。那么，可归纳证明

T(n)\le n^2

。因为，

T(n)\le\sum_{i=1}^kT(n_i)+\sum_{i=1}^kn_i\sum_{j=1}^{i-1}n_j<=\sum_{i=1}^kn_i^2+2\sum_{i=1}^k\sum_{j=1}^{i-1}n_in_j=n^2

。在加上一堆一次项和常数项后，不会改变这个阶的判断。

一个常见的错误写法如下：

CPP

int sz = 1;
for (const auto& [nt, w]: gr[cr]) {
	if (nt==pa) continue;
	auto [cnt, ndp] = dfs(dfs, nt, cr);
	for (int i = min(sz+cnt, k); i>=0; --i) {
		for (int j = 0; j<cnt && j<=i; ++j) {
			dp[i] = max(dp[i], dp[i-j]+ndp[j]+1LL*w*(j*(k-j)+(cnt-j)*(n-cnt-k+j)));
		}
	}
}

它丢掉了j的下界控制。这样会给上面的平行四边形加个小三角，变成一个梯形。这个小小的三角形看似并没有改变合并步的复杂度，但是确实给整体复杂度提升了一个阶。此时算法复杂度大致是

T(n)=\sum_{i=1}^kT(n_i)+n^2/2

。如果树大致是平衡的，那么可以参考主定理，整体算法仍然是

O(n^2)

的。但是，对于极度不平衡的树，比如一个链，算法复杂度将满足

T(n)=T(n-1)+T(1)+n^2/2

，此时必然有

T(n)=\Theta(n^3)

，将完全无法接受。

所以请控制好上下界。

为什么以及怎样用上下界优化保证平方复杂度

讨论操作

回复

相关推荐

为什么以及怎样用上下界优化保证平方复杂度