Bzoj 1009
题意：给定$m$长值域$[0,9]$数列$A_i$，要求构造$n$长值域$[0,9]$数列$X_i$使得$A_i$不是$X_i$的子串，即$X_i$中不出现$A_i$，求方案数。$n \leq 10^9, m \leq 20$

类似CF 1096D，CF 1015F以及AC自动机的相关方法，我们这里可以定义$dp(i,j)$为构造串$X_i$前$i$个字符与$A_i$匹配了$j$位的方案数。最后答案即为$\sum_{i=0}^{m-1} dp(n,i)$，即不包含完全匹配的串的方案
转移方程为(刷表)：
$$
dp(i+1,x)+=dp(i,j)
$$
$x$为在当前后面放一个$[0,9]$之间的数后匹配的影响，特别的，如果匹配了$m$位，以后转移都只能从$m$转移而来。这个$x$可用 $KMP$ 预处理。
这里$n \leq 10^9$ 显然矩阵优化，构造矩阵即可。
注意$j=0$处转移矩阵：$dp(i,0)$一定可以以某个$[0,9]$之间的数转移到$dp(i+1, 1)$，所以在矩阵中设$(0,1)=1$;
$dp(i,0)$一定可以有$9$种情况转移到$dp(i+1, 0)$，即仍然不匹配。所以在矩阵中设$(0,0)=1$

发现一个新的 $Debug$ 方法：过不去样例，可以测测自己写的小数据，这个数据可能非常小，如果程序都过不去的话，那么肯定这里都有问题。就能各个击破，发现 $Bug$。

Codeforces 1015F
题意：给你一个括号序列 $s$ （不一定是常规序列）。 括号序列是仅包含字符(和)的字符串。你的问题是计算长度为 $2n$ 的常规括号序列的数量，而且必须满足给定括号序列$ s$ 是它的子串（连续字符序列）。输出这个数量模　$ 10 ^ 9 + 7$ 的结果。

如果不考虑包含$s$，那么可以设$dp(i,j)$为构造的串前$i$个字符左括号比右括号多多少个(差值，状态冗余处理)的方案，转移非常显然

然后如果要包含子串$s$，就要引入新的维度，我们联想到CF 1096D的做法，那就是匹配状态的引入。所以我们可以设$dp(i,j,k)$为构造的串前$i$个字符左括号比右括号多多少个，并且匹配了$s$的$[1,k]$的方案数。

转移方便则刷表：
$$
\begin{cases}
dp(i+1,j+1,x)+=dp(i,j,k) \\
dp(i+1,j-1,x)+=dp(i,j,k)
\end{cases}
$$
前者为在后面插入(，后者为在后面插入)。其中的$x$为加入相应括号后$s$串的匹配状态。类似 KMP，这里如果失配了则需要找到前面最近的候选点，然后再判，所以我们利用类似KMP的方法来求解，当然也可以暴力求，但是感觉没KMP好求。注意当$k=s_{len}$时，我们只从$len$转移到$len$。

BZOJ 2288
题意：给出一个长度为$n$的数列，要求从中取出不超过$m$段连续的数，使其和最大。

首先压缩，将符号相同的压成一个元素，0随意放在任意一块位置，那么序列变为一正一负交错序列。
然后考虑没有限制$m$时，选所有正数即可。
如果有限制，我们就可以抛弃某些正数或者加入某些负数使得两个正数合成一块(注意头尾的负数不能取)
我们发现不管负数正数都只关心他的绝对值
然后对于每次操作的点他左右两边的点都是不能取的，所以转化到了Bzoj 1150

链表堆维护即可。注意记录值只需要绝对值，包括之后的任何操作！

poj 2228
题意：有一个环，选择一段长度为$n$进行计算。如果第i个时间点选择不睡觉那么就会增加$a_i$。你也可以选择睡觉，第一个时间点不算，睡觉时间至少为$m$。

先考虑线性做法，设$dp(i,j,0/1)$为前$i$个选了$j$个睡觉，$i$不选/选的最大值。
转移显然
$$
\begin{cases}
dp(i,j,0)=min(dp(i-1,j,0),dp(i-1,j,1)) \\
dp(i,j,1)=min(dp(i-1,j-1,0), dp(i-1,j-1,1)+a_i)
\end{cases}
$$
由于1位置一定不能对答案贡献，所以初值$dp(1, 0, 0)=dp(1, 1, 1)=0$，其他负无穷大
答案为$max(dp(n, b, 0), dp(n, b, 1))$
如果考虑环上做法，我们之前的做法相当于在$1$和$n$处断开了链，现在要将他强行接上去，我们可以这次强行选择$1,n$睡觉，然后再做一次DP，综合两者答案。
所以初值改为$dp(1, 0, 0)=0, dp(1, 1, 1)=a_i$，其他负无穷大
答案为$dp(n, b, 1)$
综合两者答案即可。注意要用滚动数组。

CH 5302
题意：见上。
容易想到和加分二叉树差不多，但是这里复杂了很多，不是二叉树，而且也不是 DFS 序。
观察发现对于一个子树在这个序列中还是连续的一段，并且子树对应区间最前最后两个字符必须相同，等于根节点。所以我们可以设$dp(i,j)$为$[i,j]$的答案。
为了让计数不重复，我们分问题分为$[1,k-1]$只有一颗子树，$[k,j]$可以有多棵子树。那么转移
$$
dp(i,j)=
\begin{cases}
0, S[i] ≠ S[j]\\
\sum\limits_{i+2 \leq k \leq j, S[i]=S[k]} dp(i + 1, k - 1) \cdot dp(k, j), S[i]=S[j]
\end{cases}
$$
记忆化搜索即可。

CH 5501
题意：给定$n$长数列$a$，找出最大的$a_i+a_j+min(|i-j|, n - |i-j|)$ updated on 2019.02.20

$min(|i-j|, n - |i-j|)$也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。
所以我们将环断开成一条链，然后在链上就不用讨论$\min$。

假设$i \leq j$
则对于原串上$i - j \leq \frac n2$，则$n - (i-j) > i - j$，可以对应于复制串上$i,j$之间传物品
对于原串上$i - j \geq \frac n2$，则$n - (i-j) < i - j$，可以对应于复制串上$i,j+n$之间传物品
所以直接在复制串上以区间长为$\frac n2$来处理。

对于$i$的答案为$\max(a_i+a_j+i-j)$，将定值$i$的部分提取出$\max$，那么我们只用维护$a_i-i$的最大值。因为是区间移动，所以单调队列维护。

Codeforces 1092F
题意：给定一棵有$n$个节点的树，给定每个点的点权，每个边的边权是$1$。你可以任选一个点作为$v$点，使得$\sum_{i=1}^n{dist(i,v) \cdot a_i}$最大。输出这个最大值。

二次扫描换根模板题。
显然是一个无根树最优化问题，那么逃不了DP。所以就是先随便找一个根DP一次，然后通过 DFS 再将推导出其他的答案。
本题显然能进行推导，若$v$是$u$的孩子，则

$$
\sum_{i \in 子树u}{dist(i,u) \cdot a_i}=\sum_{i \in 子树v}{(dist(i,v) +1) \cdot a_i}=\sum_{i \in 子树v}{dist(i,v) \cdot a_i+a_i}=\sum_{i \in 子树v}{dist(i,v) \cdot a_i+\sum_{i \in 子树v}a_i}
$$

设$sum(u)=\sum_{i \in 子树u}a_i$，那么$u$可以从$v$推导而来。

对于换根可以利用二次扫描换根知识和推推公式算出最后的答案。

poj 3585
题意：找一个点使得，使得从这个点出发作为源点，发出的流量最大，输出这个最大的流量。

本题是一个无根树最优化问题。朴素做法可以是枚举每个点当源点然后树形DP。
考虑随意找一个点DP后，是否其他点可以由这个答案推导出。
设$dp(u)$为以$u$为根子树的最大流量，$f(u)$为整颗树以$u$为根的最大流量。
$dp$的方程式略，具体看进阶指南上的。注意叶节点的讨论
对于$f$的计算，我们知道了$f(v)$的父亲$f(u)$，就能求出$f(v)$的值

$$
f(v)=dp(v)+min(c(x,y), f(u)-min(dp(v), c(x,y)))
$$

注意同样要特判叶节点。

然后最后答案即为$max(f(u))$

BZOJ 1999
题意：在直径上找到一个区间使得这个区间上所有点的偏心距最小。

容易想到用单调队列CF 1004E的做法。

这里其实偏心距求个最大值即可，就不用单调队列了，直接尺取。

突然发现这题和CF 1004E是一题。。

poj 1185
题意：开始时有一个由$n$个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符+或*。所有边依次用整数从$1$到$n$编号。游戏第$1$步，将一条边删除，随后$n-1$步按以下方式操作：
选择一条边$E$以及由$E$连接着的$2$个顶点$V_1$和$V_2$删除;
用一个新的顶点取代边$E$以及由$E$连接着的$2$个顶点$V_1$和$V_2$。将由顶点$V_1$和$V_2$的整数值通过边$E$上的运算得到的结果赋予新顶点;
最后，所有边都被删除。得分就是所剩顶点上的整数值。请求出这个最大的得分，以及达到的方式。

环断开一条边以后就成了链，就可以考虑DP了。我们发现简单的区间DP不满足最优子结构。和CF981D差不多，但是肯定可以改改然后还是用DP解。之前那题是改成存在性问题然后再判，这题因为负数不符合最优子结构，所以我们可以存最大值最小值转移就行了。
最大值可以从$max+max, max \cdot max$转移，而最小值可以从$min+min, min \cdot min, max \cdot min$得到。因为这些值的绝对值都是最值，所以最小值一定在这些里面。
我们断环将环复制一遍接在后面，然后每个位置开始的答案就是$[1,n], [2,n+1],…,[n, n - 1]$