P3736 [HAOI2016]字符合并
考虑区间 dp + 状压 dp。
设 \(dp(l,r,s)\) 表示 \([l,r]\) 合并成 \(s\) 的最大分数。
如果 \(r-l+1=len\)，那么合并后的长度一定是 \(len\bmod{(k-1)}\)。
于是可以考虑枚举 \(mid\)，将 \([l,mid]\) 和 \([mid+1,r]\) 的区间合并，且要求枚举的 \(mid\) 满足将 \([mid+1,r]\) 合并后只剩一个字符。
最后如果，\(len\bmod{(k-1)}=0\)，需要特殊处理全部合并的情况。
P4067 [SDOI2016]储能表
设统计大于 \(k\) 的异或和记为 \(f\)，大于 \(k\) 的方案数记为 \(g\)，答案为 \(f-k\times g\)。
\(f(i,a,b,c)\) 表示从高到低前 \(i\) 位是否与 \(n\)，\(m\) 或 \(k\) 相同的异或和。
转移的时候采用刷表法，枚举当前状态，和下一位填什么，去掉不合法的状态，转移即可。
P4124 [CQOI2016]手机号码
考虑算两次后作差。
因为不含前导零，因此先把 \(L\) 和 \(10^{10}\) 取 \(\max\)。
计算的时候不用判断前导零，以为作差直接减掉了。
设 \(dp(i,a,b,o,ok,f4,f8)\) 表示从高到低前 \(i\) 位，其中第 \(i-1\) 位为 \(b\)，第 \(i-2\) 位为 \(a\)，前 \(i\) 为是否与上界相等，是否有连续的 \(3\) 个相同的数，是否出现 \(4\) 和 \(8\) 的方案数。
P4363 [九省联考 2018] 一双木棋 chess
轮廓线 dp。
任何一种划分矩形左上三角的方式都可以看成一个长度为 \(n+m\) 的轮廓线，这样状态压缩后就非常好转移了。
P5369 [PKUSC2018]最大前缀和
设 \(sum(S)\) 表示集合 \(S\) 的和，\(f(S)\) 表示集合 \(S\) 的任意一个前缀都 \(<0\) 的方案数，\(g(S,0)\) 表示集合 \(S\) 的任意真前缀都 \(\geq 0\) 且 \(sum(S)<0\) 的方案数，\(g(S,1)\) 表示集合 \(S\) 的任意真前缀都 \(\geq0\) 且 \(sum(S)\geq 0\) 的方案数。
\[g(S,0)=g(S\oplus T,1)[sum(S)< 0] \]\[g(S,1)=g(S\oplus T,1)[sum(S)\geq 0] \]P4000 斐波那契数列
斐波那契循环节 \(\leq 6p\)，根据生日悖论，可以很快找到一个循环节。
P5772 [JSOI2016]位运算
数位 dp + 矩阵快速幂。
钦定 \(N\) 个数按照从大到小排序。
如果只有一个串，那么直接设 \(dp(i,S)\) 表示前 \(i\) 个字符，相等关系为 \(S\) 的方案数。
枚举下一个字符每个数字填什么，除去不合法的状态即可转移。
但字符串很长，不过单个字符串很短。
只有两种字符 \(0\) 或 \(1\)，且每次转移只与相等关系 \(S\) 有关，因此可以预处理出 \(2^n\times2^n\) 的转移矩阵，再使用矩阵快速幂即可解决。
P4590 [TJOI2018]游园会
如果没有最长公共子序列的限制，可以直接 dp。
有了最长公共子序列的限制，可以尝试把这一限制加入 dp 状态里。
设 \(dp(i,S,j)\) 表示前 \(i\) 个字符，最后与 “NOI” 的匹配长度为 \(l\)，前 \(i\) 个数与模式串最长公共子序列的状态为 \(S\) 的方案数。
重点在于如何压缩 \(S\)。发现差值最大为 \(1\)，于是可以状压它们的差值。
P3321 [SDOI2015]序列统计
发现选的数字个数可以合并且只和值域有关。
设 \(f(i,j)\) 表示选 \(i\) 个数字乘积为 \(j\) 的方案数。
\[f(nm,i)=\sum_{j}f(n,j)f(m,\frac{i}{j}) \]第二维是乘积的形式，不好快速求解。
可以把每个数映射到原根的指数上，那就可以卷积了。
最后再使用倍增 NTT 即可得到答案。
CF372C Watching Fireworks is Fun
设 \(dp(i,j)\) 表示放完前 \(i\) 个烟火在第 \(j\) 个区域所能获得的开心值。
\[f(i,j)=\max_{j-d(t(i)-t(i-1))\leq k\leq j+d(t(i)-t(i-1))}\{f(i-1,k)+b(i)-|a(i)-j|\} \]P4072 [SDOI2016]征途
\[\begin{aligned} S^2 &=\sum_{i=1}^{m}(v_i-\overline{v})^2\frac{1}{m}\\ &=\sum_{i=1}^{m}(v_i-\frac{sum_n}{m})^2\frac{1}{m}\\ &=\sum_{i=1}^{m}\frac{v_i^2}{m}-2sum_n\sum_{i=1}^{m}\frac{v_i}{m^2}+\left(\frac{sum_n^2}{m^2}\right) \end{aligned} \]乘上 \(m^2\) 得
\[S^2m^2=-sum_n^2+m\sum_{i=1}^{m}v_i^2 \]于是只需要 dp 求出 \(\sum_{i=1}^{m}v_i^2\) 的最小值即可。
设 \(f(i,j)\) 表示前 \(i\) 个数分成 \(j\) 段的最小值。
\[\begin{aligned} f(i,j) &=\min_{0\leq k<i}\{f(k,j-1)+(sum_i-sum_k)^2\}\\ &=\min_{0\leq k<i}\{f(k,j-1)-2sum_isum_k+sum_k^2\}+sum_i^2 \end{aligned} \]从小到大枚举 \(j\)，每次往坐标轴中加入 \((sum_k,sum_k^2+f(k,j-1))\)，用斜率为 \(2sum_i\) 的直线去切它之前的所有点，使得截距最小。
因此需要维护下凸壳。
又因为横坐标单增，斜率单增，因此可以使用双端队列维护。
P5468 [NOI2019] 回家路线
如果以点为状态进行转移的话还要加一维时间，这是不可接受的。
于是考虑以边为状态进行转移。
设 \(dp(i)\) 表示走到第 \(i\) 条边的起点的最小代价。
\[\begin{aligned} dp(i) &=\min_{y_j=x_i,q_j\leq p_i}\{dp(j)+A(p_i-q_j)^2+B(p_i-q_j)+C\}\\ &=\min_{y_j=x_i,q_j\leq p_i}\{-2Ap_iq_j+dp(j)+Aq_j^2-Bq_j\}+Ap_i^2+Bp_i+C\\ \end{aligned} \]令 \(y=kx+b\)，其中，点的坐标为 \((q_j,dp(j)+Aq_j^2-Bq_j)\)，\(k=2Ap_i\)。
要使答案最小，因此需要维护一个下凸壳。
为了满足 dp 的转移顺序，将所有边按照 \(p_i\) 从小到大排序，发现斜率也变得单增了，因此对每个 \(y_j\) 维护一个双端队列。
每次算完一个 dp 值过后把它按照 \(q_j\) 放到一个桶里，当时间到 \(q_j\) 时才把它加入双端队列里。这样，既满足了横坐标的单调性，又满足了 \(q_j\leq p_i\) 的顺序性。
CF321E Ciel and Gondolas
设 \(dp(i,j)\) 表示前 \(i\) 条船送走前 \(j\) 个人的最小代价。
\[dp(i,j)=\min_{0\leq k<j}\{dp(i-1,k)+w(k+1,j)\} \]\(w(l,r)\) 满足区间包含单调性和四边形不等式，因此可以使用分治优化。
！P5206 [WC2019] 数树
独立地推一遍式子！
P2150 [NOI2015] 寿司晚宴
经典套路，采用根号分治，因为 \(>\sqrt{n}\) 的质数最多只会出现一次，因此只需要状压 \(\leq\sqrt{n}\) 的质数。
设 \(dp(i,S1,S2)\) 表示选了前 \(i\) 个数，质数状态为 \(S1\) 和 \(S2\) 的方案数。
如果 \(i\) 的质因子都 \(\leq \sqrt{n}\)。
\[dp(i-1,S1,S2)\longrightarrow dp(i,S1|s(i),S2)\\ dp(i-1,S1,S2)\longrightarrow dp(i,S1,S2|s(i)) \]如果 \(i\) 存在 \(>\sqrt{n}\) 的质因子。
可以把所有数按照大质因子排序，连续的一段区间一定是同一个人选。
对是哪一个人选分别 dp 即可。
P6622 [省选联考 2020 A/B 卷] 信号传递
首先，贡献可以拆成每个信号站之间的贡献。
设 \(i\) 号的位置为 \(p_i\)。
如果有 \(x\longrightarrow y\) 的边，那么贡献为
- 如果 \(p_x\leq p_y\)，\(p_y-p_x\)
- 如果 \(p_x>p_y\)，\(k(p_x+p_y)\)。
于是可以预处理出 \(e(x,y)\) 表示 \(x\longrightarrow y\) 的边数。
设 \(f(S)\) 表示前 \(|S|\) 个位置，选择的点的集合为 \(S\) 的最小时间。
\[f(S+i)=\min_{i\notin S}f(S)+(|S|+1)\left(\sum_{j\in S}e(i,j)\times k+e(j,i)+\sum_{j\notin S}-e(i,j)+e(j,i)\times k\right) \]时间复杂度为 \(O(2^mm^2)\)，无法通过本题，考虑预处理。
发现每次转移只和 \(i\) 与 \(S\) 有关，于是预处理 \(g(S,i)(i\notin S)\) 满足
\[f(S+i)=\min_{i\notin S}f(S)+(|S|+1)g(S,i) \]可以考虑选择一个 \(j=lowbit(S)\)。
\[g(S,i)=g(S-j,i)+e(i,j)\times k+e(j,i)-(-e(i,j)+e(j,i)\times k) \]P7519 [省选联考 2021 A/B 卷] 滚榜
很明显，如果 \(a\) 的排列确定，可以贪心地选取以尽量使 \(\sum b_i\) 尽量小。
考虑如何计算 \(b_i\) 和的最小值
\[\sum_{i=1}^{n}b_i=\sum_{i=2}^{n}\max(0,a_{p_i}-a_{p_{i-1}}+[p_i>p_{i-1}])\times(n-i+1) \]于是可以设 \(dp(S,i,j)\) 表示选的数前 \(|S|\) 个数的集合为 \(S\)，其中第 \(|S|\) 个为 \(i\)，\(b\) 的总和为 \(j\) 的方案数。
枚举下一个数选什么即可转移。
标签：10,frac,省选,S2,sum,times,leq,动态,dp From： https://www.cnblogs.com/yanchengzhi/p/17002012.html