dp - IPS99技术分享

标签：sz last int dfs 考虑 dp

前情提要

dp 专题复习

树形 dp

其实对我来说树形 dp 会比序列 dp 学得好一些，因为树是有一个具体形态的东西，推式子是比较具象的。其实序列就是把树拍平在数轴上去 dp 的，只要考虑到这一点，画出 dp 的转移图，式子就可以呼之欲出了。

不套路的 dp

考验人类智慧的时刻到了！

P1352 没有上司的舞会

树的最大独立集。

比较典的一道题目，有限制的的话考虑设状态为 0/1，在树上转移即可。考虑转移顺序，因为是父亲影响儿子，所以是自上而下转移的。

P2016 战略游戏

树的最小点覆盖。

与前一题的相似，考虑状态设成 0/1 形式。同样的是父亲影响儿子，正常转移即可。

换根 dp

比较套路的树形 dp。一般转移过程与树根有关又没有钦定树根时可以考虑使用。

P3478 POI2008 STA-Station

考虑随便选点为根进行答案的求取。接下来考虑换根对答案的贡献（这一部分一定要画图 & 细心！有时候以不同点为根的变量的定义是不同的！），对答案求 \(\max\) 即可，显然是线性做法。

CF1187E Tree Painting

同上。

树形背包

人类智慧大开发！

基于 dfs 合并

\(\circ\) 物品大小为 \(1\)，没有限制

inline void dfs(int x, int last) {
  for(auto u : g[x])
    if(u != last) {
      dfs(u, x);
      
      for(int i = 0 ; i <= sz[x] ; ++ i)
        for(int j = 0 ; j <= sz[u] ; ++ j)
          dp[x][i + j] = dp[x][i] + dp[u][j];

      sz[x] += sz[u];
    }
}

由于点对 \((u, v)\) 只会在 \(lca\) 处考虑到，因而时间复杂度 \(O(n ^ 2)\)。

\(\circ\) 有物品大小

inline void dfs(int x, int last) {
  sz[x] = c[x];
	dp[x][c[x]] = w[x];
	
	for(auto u : g[x])
		if(u != last) {
			dfs(u, x);
			
			sz[x] += sz[u];
			
			for(int i = min(sz[x], LIM) ; i >= c[x] ; -- i)
				for(int j = min(sz[u], min(i - c[x], LIM)) ; j >= c[u] ; -- j)
					dp[x][i] = max(dp[x][i], dp[x][i - j] + dp[u][j]);
		}
}

可以被卡到 \(O(n ^ 2w)\)，其中 \(w\) 为物品大小。

\(\circ\) 物品大小为 \(1\)，有 \(k\) 的限制

inline void dfs(int x, int last) {
	for(auto u : g[x])
		if(u != last) {
			dfs(u, x);
			
			for(int i = m ; ~ i ; -- i)
				for(int j = 0 ; j <= i - 1 ; ++ j)
		    		dp[x][i] = max(dp[x][i], dp[x][i - j] + dp[u][j]);
		}
}

此时的时间复杂度是 \(O(nm ^ 2)\) 的，考虑优化。

实际上，这里面有很多状态都是没有意义的：

1.转移时已经合并了大小之和为 \(S\) 的一些子树，那么 \(dp_{x, i} (i > S)\) 是没有意义的。

2.\(dp_{u, i} (i > sz_u)\) 也是没有意义的。

3.\(dp_{x, i}(i > m)\) 也是没有意义的。

所以可以考虑对转移时的两重循环进行上下界优化：

inline void dfs(int x, int last) {
	sz[x] = 1;
	
	for(auto u : g[x])
		if(u != last) {
			dfs(u, x);
			
			for(int i = min(m, sz[x] + sz[u]) ; ~ i ; -- i)
				for(int j = max(0ll, i - sz[x]) ; j < i && j <= sz[u] ; ++ j)
		    		dp[x][i] = max(dp[x][i], dp[x][i - j] + dp[u][j]);
		  
		  sz[x] += sz[u];
		}
}

因为每个点对只会在 \(lca\) 处考虑到，因此时间复杂度是 \(O(n ^ 2)\) 的。

证明见link。

还要注意实际上你每棵子树是可以不选的所以在枚举的时候需要注意边界。

基于 dfs 序上 dp

设 \(dp_{i,j}\) 表示考虑到第 \(i\) 个，剩余容量为 \(j\) 的状态。

有两种转移：

\(\circ\) 不选 \(i\)，那么 \(i\) 的子树都不能选，转移到 \(dp_{i + sz_i, j}\)。

2、选 \(i\)，那么按照 dfs 序考虑下一个，转移到 \(dp_{i + 1, j - c} + w\)。

正确性显然。

不足之处是，有些树上的信息无法知道。

因为是放到了序列上去讨论的，所以应该是很好理解的。

代码还在咕。

环状 dp

断环成链

经典，不多讲，去看 dp 专题复习。

对相接处讨论

P6064 [USACO05JAN] Naptime G

因为答案与之前是否入睡有关，所以状态设个 0/1。由于时间是无限循环的，所以断环成链是显然不方便的。我们考虑对拼接处进行讨论。于是只要 dp 两次就行了。

正难则反

P1121 环状最大两段子段和

分两种情况：

最大两段子段和不跨越相接处

同时维护前后缀的最大子段和，枚举断点即可。

跨越

直接去维护是很难的。但考虑到它不是一个循环序列，所以用容斥思想去求最小两段子段和即可。

状压 dp

博客。

通常是设一个二进制状态表示物品的取舍从而去转移。所以实际上其状态总数是没有变的，状压过程只是让状态排列的更加紧密了。

在 OI 中，一般对网格图上的状压考察较多。

子集枚举

题目：

给定一个长度为 \(n\ (n\le15)\) 的排列，问此排列中的 \(n\) 个元素所组成的每一个集合的所有子集。

考虑暴力枚举一下。

for(int S=0;S<=(1<<n);S++)
   for(int T=0;T<=S;T++)
  	   ...

显然此时复杂度是 \(O(4^n)\) 的。

但是写成这样的形式能将复杂度降至 \(O(3^n)\)：

for(int S=0;S<=(1<<n);S++)
	for(int T=S;T;T=(T-1)&S)
		...

先考虑证明复杂度：

\(n\) 位选出 \(k\) 位的方案数有 \((_{n}^{k})\) 个，\(k\) 位的子集个数有 \(2^k\) 个

所有集合的子集的元素个数和为 \(\sum_{k=0}^{n}(_{n}^{k})\times 2^{k}\)（不妨 \(k=0\) 也计算在内）

将上式变形得：

\[\sum_{k=1}^{n}(_{k}^{n})\times 1^{n-k}\times 2^{k} \]

二项式定理知为 \(O(3^n)\)。

再证明一下正确性：

考虑 \(S\) 的子集，在二进制上从大到小排成一排，那么大的通过减若干个 \(1\) 就一定能到小的，

但是中间会产生大量的状态，这些状态中包含了一些 \(S\) 中不包含的 \(1\)，故和 \(S\) 与一下，去冗即可。

从而每两个相邻的状态就都是 \(S\) 的子集，由于降序从而任意两个状态不重复，即任意子集状态均可达。

变相的搜索

P3052 [USACO12MAR] Cows in a Skyscraper G

在此题中，\(n\) 个物品的取舍是与答案相关的，而我们又发现 \(n\) 的范围很小，所以可以考虑状压 dp。

设 \(dp_{i,j}\) 将物品分成 \(i\) 组，\(n\) 个物品的取舍的不同的每组总体积小于等于 \(W\) 的第 \(i\) 组的总体积，其中 \(j\) 为二进制数。

那么很显然我们就可以通过枚举 \(n·2^n\) 个状态去进行转移了。

标签：sz,last,int,dfs,考虑,dp
From： https://www.cnblogs.com/endswitch/p/18375717

dp