Training 5: Dynamic Programming

Problem A

Solved by Xiejiadong.

题意：求区间 \([L,R]\) 内满足相邻两位的差 \(\ge 2\) 的数的个数。

题解：这道题目的前导 \(0\) 有点难处理。

\(f[i][j][k][m]\) 表示处理到第 \(i\) 位，第 \(i\) 位上的数为 \(j\) ，\(k=0/1\) 前 \(i\) 位是否于上限一致，\(m=0/1\) 是否有前导 \(0\) 。

直接转移可以得到区间 \([1,x]\) 的总数，查分并检验下限是否满足要求即可。

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.