山西省建设厅网站 孙涛,seo见到效果再付费,朵朵软件网站建设,网页设计与制作教程哪里有看证明#xff1a;有依赖背包结点数优化后为 O ( n 2 ) O(n^2) O(n2)
siz[u]表示以u为根的树的结点数 深搜过程中#xff0c;siz[u]表示根结点为u的树的根结点加上前i个子树的结点数。
根结点为u的树取前i个子树的结点#xff0c;取到的结点数量小于等于siz[u]根结点为v的子…证明有依赖背包结点数优化后为 O ( n 2 ) O(n^2) O(n2)
siz[u]表示以u为根的树的结点数 深搜过程中siz[u]表示根结点为u的树的根结点加上前i个子树的结点数。
根结点为u的树取前i个子树的结点取到的结点数量小于等于siz[u]根结点为v的子树取到的结点数量小于等于siz[v]
例 洛谷 P2014 [CTSC1997] 选课 使用结点数优化
#includebits/stdc.h
using namespace std;
#define N 305
int n, m, w[N], siz[N], dp[N][N];//dp[u][i][j]结点u的前i个孩子最多选择j门课能获得的最大学分
vectorint edge[N];
void dfs(int u)
{dp[u][1] w[u];//选1门课就只能选自己 siz[u] 1;for(int v : edge[u]){dfs(v);siz[u] siz[v];for(int j min(m, siz[u]); j 1; --j)//在树中选j门课 for(int k 0; k j k siz[v]; k)//在子树v中选了k门课 因为还要选v最多选j-1门 dp[u][j] max(dp[u][j], dp[u][j-k]dp[v][k]); }
}
int main()
{int f;cin n m;m;//算上0号结点 for(int i 1; i n; i){cin f w[i];edge[f].push_back(i);}dfs(0);cout dp[0][m];return 0;
}假设m很大不考虑j的影响其核心代码可以视作
void dfs(int u)
{dp[u][1] w[u];//选1门课就只能选自己 siz[u] 1;for(int v : edge[u]){dfs(v);siz[u] siz[v];for(int j siz[u]; j 1; --j)for(int k 0; siz[v]; k)dp[u][j] max(dp[u][j], dp[u][j-k]dp[v][k]); }
}设根结点为u的树的结点数量为n 证明上述代码的复杂度为 O ( n 2 ) O(n^2) O(n2) 设结点u有k个子树1、2、3、…、k 每个子树的结点数分别为 a 1 , a 2 , . . . , a k a_1, a_2, ..., a_k a1,a2,...,ak因此有 a 1 a 2 . . . a k n − 1 a_1a_2...a_k n-1 a1a2...akn−1 该代码中双重循环内层语句的运行次数近似为 a 1 ∗ a 1 ( a 1 a 2 ) ∗ a 2 ( a 1 a 2 a 3 ) ∗ a 3 . . . ( a 1 . . . a k ) ∗ a k a_1*a_1(a_1a_2)*a_2(a_1a_2a_3)*a_3...(a_1...a_k)*a_k a1∗a1(a1a2)∗a2(a1a2a3)∗a3...(a1...ak)∗ak 使用数学归纳法
如果结点u的孩子都是叶子结点则 a 1 , a 2 , . . . , a k a_1, a_2, ..., a_k a1,a2,...,ak都为1那么语句运行次数为 1 2 . . . k ( 1 k ) ⋅ k / 2 ≤ k 2 12...k (1k)\cdot k/2 \le k^2 12...k(1k)⋅k/2≤k2如果结点u的孩子不都是叶子结点对于子树x的递归调用语句运行次数 ≤ a x 2 \le a_x^2 ≤ax2因此总语句运行次数 ≤ a 1 ∗ a 1 ( a 1 a 2 ) ∗ a 2 ( a 1 a 2 a 3 ) ∗ a 3 . . . ( a 1 . . . a k ) ∗ a k a 1 2 a 2 2 . . . a k 2 \le a_1*a_1(a_1a_2)*a_2(a_1a_2a_3)*a_3...(a_1...a_k)*a_ka_1^2a_2^2...a_k^2 ≤a1∗a1(a1a2)∗a2(a1a2a3)∗a3...(a1...ak)∗aka12a22...ak2 将前面每项写开 a 1 2 a_1^2 a12 a 1 ∗ a 2 a 2 2 a_1*a_2a_2^2 a1∗a2a22 a 1 ∗ a 3 a 2 ∗ a 3 a 3 2 a_1*a_3a_2*a_3a_3^2 a1∗a3a2∗a3a32 … a 1 ∗ a k . . . a k 2 a_1*a_k...a_k^2 a1∗ak...ak2 相加得 a 1 ∗ ∑ i 1 k a i a 2 ∗ ∑ i 2 k a i a 3 ∗ ∑ i 3 k a i . . . a k ∗ a k a_1*\sum_{i1}^k{a_i}a_2*\sum_{i2}^k{a_i}a_3*\sum_{i3}^k{a_i}...a_k*a_k a1∗∑i1kaia2∗∑i2kaia3∗∑i3kai...ak∗ak a 1 ∗ ∑ i 1 k a i a 2 ∗ ∑ i 1 k a i a 3 ∗ ∑ i 1 k a i . . . a k ∗ ∑ i 1 k a i ( ∑ i 1 k a i ) 2 ( a 1 a 2 . . . a k ) 2 ( n − 1 ) 2 n 2 a_1*\sum_{i1}^k{a_i}a_2*\sum_{i1}^k{a_i}a_3*\sum_{i1}^k{a_i}...a_k*\sum_{i1}^k{a_i} (\sum_{i1}^k{a_i})^2 (a_1a_2...a_k)^2(n-1)^2n^2 a1∗∑i1kaia2∗∑i1kaia3∗∑i1kai...ak∗∑i1kai(∑i1kai)2(a1a2...ak)2(n−1)2n2 而 a 1 2 a 2 2 . . . a k 2 ( a 1 a 2 . . . a k ) 2 ( n − 1 ) 2 n 2 a_1^2a_2^2...a_k^2 (a_1a_2...a_k)^2(n-1)^2n^2 a12a22...ak2(a1a2...ak)2(n−1)2n2 因此语句总运行次数 2 n 2 2n^2 2n2 因此该算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
