START202——Counting Graphs

思路讲解

（现在看起来，这个题目有一点难了，超出了我的理解范围）

说实话，看这道题目，真一点思路都没有，连图都没有，我怎么动态规划？

那么一个联通块作为一个大块是非常难做的，那有没有可能分成好几个小块那？可以的兄弟，可以的，把 1 删除以后，就形成了一个个的小块。这些小块的访问顺序就是

$A[l_i],A[l_i+1]…,A[r_i]$

注意到，我们可以要求这些小块互不连通，那你说联通的情况怎么办呢？怎么统计那？

哈哈，这就用到了一个小巧思，把这个看作为联向 1 的回边，这样我们就能保证小块之间不联通（指的是删除点 1 后）。

想到这个了，我们就会发现，在保持现有联通块及其访问顺序的情况下，哪些点可以连回 1 那？这个其实也很简单，大于 $A[l_i]$ 即可。

然后题目说，我们现在已经成功的把一个大问题分解为小问题了，那不妨用 dp 继续。

Observe that we’ve really just broken the original problem down into smaller problems of the same nature - which naturally suggests dynamic programming.

呃，其实我觉得和分治思想差不多，就是继续把 $A[l_i]$ 当根。

然后我们不难发现，这个重点就在于怎么样求这个块的划分方法那？

其实这个递推式子是不难的，是符合直觉的，但是确实比较难绷。

因为整了两个数组，dp（dp[i][j] 表示从 i 到 j 的答案） 和 split（split[i][j] 表示从 i 到 j 有多少种划分方法） 实际上是一个东西（忽略联向根的回边），就是有一个差一，即：

$split[i+1][j]=dp[i][j]$

那么我们怎么递推得到 $split$ 那？其实也简单，不难发现（忽略联向根的回边）：

$$dp[L][R]=split[L+1][R]=\sum^{R}_{x=L+1}dp[L+1][x]\cdot split[x+1][R]\cdot \\ [A_{L+1}<A_{x+1}]（为真时是1，反之为0）$$

这个式子看起来非常天外飞仙，其实很简单，就是把所有的分块都尝试一遍。

之所以分为两个，是为了避免差一错误。

你可能还会想，为什么一开始是 $dp[L+1][x]$ 那？首先不用 split 是为了避免 $split[L+2][L+1]$ 这种诡异的情况出现，然后 $A[L+1]$ 是一定要为根的，因此用dp[L+1][x]。

那为什么后面一个代码是 $split[x+1][R]$ ，而不是 $dp[x+1][R]$ ？我也想了一会儿，不难发现 $split[x+1][R]$ 可以保证 x+1 一定是根，但是不保证 x+2 一定是根，而采用 $dp[x+1][R]$ 会导致不仅 x+1 一定是根，x+2 也一定是根。

好，那么现在问题就来到了我们怎么样实现了。题解给了一种比较好的实现方法，就是先枚举长度，再枚举起始点，因为不难发现长的区间是从短的区间转移过来的。

我感觉题解给的式子有点麻烦了，而且有点奇怪。

AC代码

源代码

心路历程（WA，TLE，MLE……）