Difference between revisions of "Training 5: Dynamic Programming"

From EOJ Wiki
Jump to navigation Jump to search
Line 17: Line 17:
 
题意:给定一个 $n$ $(1 \le n \le 16)$ 个点,有重边且每条边都不一样的无向图,求联通无重边子图的个数。
 
题意:给定一个 $n$ $(1 \le n \le 16)$ 个点,有重边且每条边都不一样的无向图,求联通无重边子图的个数。
  
题解:令 $S$ 是 $\{1,\dots,n\}$ 的子集,$cnt(S)$ 代表 $S$ 的子图数量,$ans(S)$ 代表 $S$ 的连通子图数量,$cnt(S)$ 可以通过枚举边计算,$ans(S)$ 可以枚举第一个点所在的极大连通块 dp 得到结果。按 $|S|$ 从小到大 dp,最后 $ans(\{1,\dots,n\})$ 就是答案。
+
题解:令 $S$ 是 $\{1,\dots,n\}$ 的子集,$cnt(S)$ 代表 $S$ 的子图数量,$ans(S)$ 代表 $S$ 的连通子图数量,$cnt(S)$ 可以通过枚举边计算,$ans(S)$ 可以枚举第一个点所在的极大连通块 dp 得到结果。按 $|S|$ 从小到大 dp,$ans(\{1,\dots,n\})$ 就是答案。
  
 
== Problem E ==
 
== Problem E ==

Revision as of 10:33, 12 September 2019

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by Kilo_5723.

题意:给定一个 $n$ $(1 \le n \le 16)$ 个点,有重边且每条边都不一样的无向图,求联通无重边子图的个数。

题解:令 $S$ 是 $\{1,\dots,n\}$ 的子集,$cnt(S)$ 代表 $S$ 的子图数量,$ans(S)$ 代表 $S$ 的连通子图数量,$cnt(S)$ 可以通过枚举边计算,$ans(S)$ 可以枚举第一个点所在的极大连通块 dp 得到结果。按 $|S|$ 从小到大 dp,$ans(\{1,\dots,n\})$ 就是答案。

Problem E

Unsolved.

Problem F

Unsolved.