DP练习

标签：方案 frac sum 练习 矩阵 times DP dp

P3628 [APIO2010]特别行动队

设\(f_i\)表示已经分好了前\(i\)个士兵所获得的最大战斗力，可以写出dp式子

\[f_i=\max_{j=0}^{i-1}f_j+a(s_i-s_j)^2+b(s_i-s_j)+c \]

考虑斜率优化

\[f_i=f_j+a(s_i-s_j)^2+b(s_i-s_j)+c \]

\[f_i=f_j+a\times s_i^2-a\times 2s_is_j+a\times s_j^2+b\times s_i-b\times s_j+c \]

考虑什么情况下一个决策点会比另一个更优

\[f_j-a\times 2s_is_j+a\times s_j^2-b\times s_j\le f_k-a\times 2s_is_k+a\times s_k^2-b\times s_k \]

\[s_i(a\times 2s_k-a\times 2s_j)\le f_k-f_j+s_k^2-s_j^2-s_k+s_j \]

\[s_i\le \frac{f_k-f_j+s_k^2-s_j^2-s_k+s_j}{a\times 2s_k-a\times 2s_j} \]

因为\(s_i\)是单调递增的，所以不等式右侧也要是单调递增的，用单调队列维护即可

P5504 [JSOI2011] 柠檬

首先发现一个性质，每个小段的左右端点大小一定相同，且这一段的\(s_0\)一定是左右端点的大小

写出式子

\[f_i=\max_{j=1}^{i}f_{j-1}+s_i(c_i-c_j+1) \]

其中\(c_i\)表示该位置的柠檬是相同大小的第几个
斜率优化可得

\[s_ic_i\le \frac{f_{k-1}+s_kc_k^2-2s_kc_k-f_{j-1}-s_jc_j^2+2s_jc_j}{2c_k-2c_j} \]

P3648 [APIO2014]序列分割

发现答案和分割的顺序无关，只和分割的位置有关

设\(f_{i,j}\)表示前\(i\)个元素分成\(j\)个块的最大分数，滚动掉第二维

\[f_i=\max_{j=0}^{i-1}f_j+s_j(s_i-s_j) \]

斜率优化可得

\[s_i\le \frac{f_k-s_k^2-f_j+s_j^2}{s_j-s_k} \]

P2657 [SCOI2009] windy 数

将询问区间\([a,b]\)转化为\([1,a-1]\)和\([1,b]\)

数位dp，使用记忆化搜索写法

设\(dp[i][j][0/1][0/1]\)表示从高到低第\(i\)位，前一位数字是\(j\)，之前的数是否与最大值相同，有无前导零

P2602 [ZJOI2010]数字计数

dp数组含义同上，对于每一个数码dp一次

P4124 [CQOI2016]手机号码

设\(dp[i][j][k][0/1][0/1][0/1][0/1]\)表示从高到低第\(i\)位，前一位数字是\(j\)，前前一位数字是\(k\)，之前是否出现过\(4\)，是否出现过\(8\)，之前的数是否与最大值相同，是否出现过连续三个相同

P1654 OSU!

若当前已经有了\(x\)个连续的\(1\)，考虑再增加一个\(1\)对于答案贡献的期望

\[(x+1)^3=x^3+3x^2+3x+1 \]

\[(x+1)^2=x^2+2x+1 \]

分别维护\(x^3\)，\(x^2\)，\(x\)

\[x1_i=(x1_{i-1}+1)\times p_i \]

\[x2_i=(x2_{i-1}+2\times x1_{i-1}+1)\times p_i \]

\[ans_i=ans_{i-1}+(3\times x2_{i-1}+3\times x1_{i-1}+1)\times p_i \]

CF235B Let's Play Osu!

双倍经验

P4550 收集邮票

设\(f_i\)表示已经获得了\(i\)种邮票，还需要几次才能获得所有邮票，显然\(f_n=0\)

\[f_i=1+\frac{i}{n}\times f_i+\frac{n-i}{n}\times f_{i+1} \]

\[f_i=f_{i+1}+\frac{n}{n-i} \]

设\(g_i\)表示已经获得了\(i\)种邮票，还需要多少钱才能获得所有邮票，显然\(g_n=0\)

\[g_i=\frac{i}{n}\times (g_i+f_i+1)+\frac{n-i}{n}\times (g_{i+1}+f_{i+1}+1) \]

\[g_i=g_{i+1}+f_{i+1}+\frac{i}{n-i}\times f_i+\frac{n}{n-i} \]

P3802 小魔女帕琪

这道题不是dp题，但有助于对概率期望加深理解

考虑前七个各不相同的概率

\[\frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6} \]

一共有\(7!\)种排列，所以前七个的贡献是

\[7!\times \frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6} \]

现在考虑第\(2-8\)个各不相同的概率

假设第一个为\(a_1\)

\[\frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6}\times \frac{a_1-1}{N-7} \]

同样第\(2-8\)个有\(7!\)种排列

\[7!\times \frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times \frac{a_7}{N-6}\times \frac{a_1-1}{N-7} \]

第一个为\(a_2\)

\[7!\times \frac{a_2}{N}\times \frac{a_3}{N-1}\times \frac{a_4}{N-2}\times \frac{a_5}{N-3}\times \frac{a_6}{N-4}\times \frac{a_7}{N-5}\times \frac{a_1}{N-6}\times \frac{a_2-1}{N-7} \]

以此类推，发现每个式子的最后一项加起来是\(1\)

所以第\(2-8\)个各不相同的概率与\(1-7\)个相同，所以最终答案为

\[7!\times \frac{a_1}{N}\times \frac{a_2}{N-1}\times \frac{a_3}{N-2}\times \frac{a_4}{N-3}\times \frac{a_5}{N-4}\times \frac{a_6}{N-5}\times a_7 \]

P3232 [HNOI2013]游走

考虑贪心，将每条边按照期望经过次数由大到小排序，然后由大到小编号

由于边数太大，将边的期望经过次数\(g_i\)转化为点的期望经过次数\(f_i\)

\[g_i=\frac{f_v}{\deg_v}+\frac{f_u}{\deg_u}(u\neq n,v\neq n) \]

现在的问题就是计算\(f\)数组

\[f_u=\begin{cases}\sum_{(u,v)\in Edge}\frac{f_v}{\deg_v}+1,u=1\\\sum_{(u,v)\in Edge}\frac{f_v}{\deg_v},1<u<n \end{cases} \]

高斯消元计算即可

P3750 [六省联考2017]分手是祝愿

先考虑最优策略是什么

发现对于当前编号最大的开着的灯，直接关掉它一定是最优的，所以只要从大到小扫一遍，遇到亮的就关掉，最后的操作方案就是最优的，我们只要求出做完这些操作的期望操作次数就行

设\(f_i\)表示从还剩\(i\)个操作到还剩\(i-1\)个操作的期望次数

\[f_i=\frac{i}{n}\times 1+\frac{n-i}{n}\times (f_i+f_{i+1}+1) \]

\[f_i=\frac{n+(n-i)\times f_{i+1}}{i} \]

如果最开始的最优操作次数小于k，那么答案就是这个次数，否则答案就是\(f_{cnt}+f_{cnt-1}+...+f_{k+1}+k\)，最后再乘上\(n!\)即可

P4284 [SHOI2014]概率充电器

因为每个结点的的贡献为\(1\)所以这道题的期望就是概率

考虑一个结点可以如何充电

1. 自己给自己充

2. 自己的儿子给自己充

3. 自己的父亲给自己充

因为既有儿子的贡献又有父亲的贡献，所以要用到树形dp的up and down

设\(f_i\)为\(i\)号节点充电的概率，初始为\(f_i=q_i\)

• 先考虑up，即儿子给父亲充电

如何合并两个结点的值

设一个事件发生的概率为\(P(A)\)，另一个事件发生的概率为\(P(B)\)，则这两个事件至少有一个发生的概率为

\[P(A)+P(B)-P(A)\times P(B) \]

所以转移方程为

\[f_u=f_u+f_v\times p(u,v)-f_u\times f_v\times p(u,v) \]

• 然后考虑down，即父亲给儿子充电

设\(P(B)=f_v\times p(u,v)\)

\[f_u=P(A)+P(B)-P(A)\times P(B) \]

\(P(A)\)即为\(u\)除了\(v\)这棵子树外的子树对\(u\)的贡献

\[P(A)=\frac{f_u-P(B)}{1-P(B)} \]

\[f_v=f_v+P(A)\times p(u,v)-f_v\times P(A)\times p(u,v) \]

P3272 [SCOI2011]地板

插头dp模版

先考虑状态表示：\(0\)表示没有被穿过，\(1\)表示被穿过且穿过前没有拐弯，\(2\)表示被穿过且穿过前拐过弯

考虑如何转移

1. \(11\Rightarrow 00\)

2. \(01\Rightarrow 02/10\)

3. \(10\Rightarrow 20/01\)

4. \(02\Rightarrow 00/20\)

5. \(20\Rightarrow 00/02\)

6. \(00\Rightarrow 22/10/01\)

P3622 [APIO2007] 动物园

考虑状压，每个围栏里的动物可以选择不撤走或撤走，用\(0/1\)表示

但围栏总数有\(10^4\)个，不能用状压表示，但我们发现每个小朋友只能看到\(5\)个围栏，于是可以每\(5\)个围栏状压一下

设\(f[i][s]\)表示\(\{i,i+1,i+2,i+3,i+4\}\)这几个围栏中动物被移走的状态为\(s\)的最大开心的小朋友数量，于是可以写出dp式子

\[f[i][s]=max(f[j-1][(s\And 15)<<1],f[j-1][(s\And 15)<<1|1])+g[j][s] \]

其中\(g[i][s]\)是预处理出来的数组，表示观看范围为\(\{i,i+1,i+2,i+3,i+4\}\)这些围栏的小朋友中，当这些围栏的状态为\(s\)时有多少时开心的

P3204 [HNOI2010] 公交线路

可以将问题转化为有一个长度为\(N\)的序列，每个位置要填充一个\([1,K]\)的数，对于任意的\(1\leq i\leq K\)，序列的第\(i\)个位置已经被填充，填充的数为\(i\)，同时\([N-K+1,N]\)区间内填充的数必须包含\([1,K]\)的所有数，序列中任意一个长度为\(P\)的一段，都必须填充有\([1,K]\)的所有数

发现\(K\)和\(P\)都比较小，所以可以考虑状压dp，设\(f[i][s]\)表示\(\{i,i+1,...,i+P-1\}\)这些位置填充的状态为\(s\)的方案数

因为我们保证每个时刻s表示的区间填充的数都各不相同，所以并不用记录填了那些数，只需要关心填了那些位置，同时，因为要保证每个位置都被填充，所以\(s\)的最高位始终都要是\(1\)

也可以理解为每次转移都是让最靠后的那辆车走到他的下一个停靠点

但这个dp是无法通过此题的，我们发现每个状态能转移到那些状态是固定的，所以考虑矩阵优化

构造矩阵\(f[i][j]\)，若编号\(i\)的状态可以转移到编号为\(j\)的状态，\(f[i][j]\)就为\(1\)，最后进行\(N-K\)次矩阵快速幂，再乘上初始矩阵即可

P3226 [HNOI2012]集合选数

构造一个矩阵，第一行第一列的数为\(1\)，每个数横行的下一个数是这个数的两倍，每个数竖列的下一个数是这个数的三倍，问题转化为在这个矩阵里选一些数，相邻的数不能选

发现矩阵的长和宽都是\(\log\)级别的，所以考虑状压dp，对\(n\)以内所有不是\(2\)和\(3\)倍数的数构造矩阵，最后乘法原理相乘即可

P2470 [SCOI2007]压缩

可以发现，在一个字符串中插入一个\(M\)，表示将这个字符串分成了独立的两部分，每个部分相当于一个可以独立计算的新字符串，于是我们可以通过\(M\)将大区间分为子区间，这就是区间dp的本质

设\(f_{i,j,0/1}\)表示区间\([i,j]\)的答案，\(0\)表示无\(M\)，\(1\)表示有\(M\)

先考虑\(f_{i,j,0}\),若前半段和后半段相等，那么

\[f_{i,j}=\min(f_{i,j,0},f_{i,mid,0}+1) \]

然后枚举中间点转移

\[f_{i,j,0}=\min(f_{i,j,0},f_{i,k,0}+j-k) \]

然后考虑\(f_{i,j,1}\)，枚举在那个点插入\(M\)

\[f_{i,j,1}=\min(f_{i,j,1},\min(f_{i,k,0},f_{i,k,1})+\min(f_{k+1,j,0},f_{k+1,j,1})+1) \]

最后答案为\(\min(f_{1,n,0},f_{1,n,1})\)

P4158 [SCOI2009]粉刷匠

区间dp，设\(f_{i,j}\)表示前\(i\)个木板，粉刷\(j\)次最多能正确粉刷的格子数，\(g_{i,j,k}\)表示第\(i\)个木板，粉刷\(j\)次，刷了前\(k\)个格子，最多能正确粉刷的格子数

\[f_{i,j}=\max(f_{i,j},f_{i-1,j-k}+g_{i,k,m}) \]

\[g_{i,j,k}=\max(g_{i,j,k},g_{i,j-1,l}+\max(sum_{i,k}-sum_{i,l},k-l-sum_{i,k}+sum_{i,l})) \]

用\(sum_{i,j}\)表示第i块木板前j个格子应该被粉刷多少个蓝色格子，相当于前缀和

P1450 [HAOI2008]硬币购物

多重背包模型，但直接多重背包做肯定会超时，多重背包和完全背包的不同就在于多重背包限制了每种物品选择的次数，只有\(4\)种物品，完全背包是可做的，所以先考虑没有次数限制的情况

\[f[j]=f[j]+f[j-c_i] \]

然后要减去不合法的，考虑第\(i\)种物品取了超过\(d_i\)的情况,即\(f[s-c_i\times (d_i+1)]\)

可以理解为先取出\(d_i+1\)个\(i\)物品，之后随便取，这样就保证了\(i\)物品一定超过\(d_i\)

用\(f[s]\)先减去每一种物品取多的情况，再加上每两种物品取多的情况，再减去每三种物品取多的情况，再加上每四种物品取多的情况就是答案

P5664 [CSP-S2019] Emiya 家今天的饭

合法的方案数不好算，所以考虑用总方案数减去不合法的方案数

发现如果存在列不合法，一定只有一列不合法，因为不可能有两列都超过总个数的一半

所以可以枚举不合法的列，设\(f_{i,j,k}\)表示前\(i\)行在当前列选了\(j\)个数，在其他列选了\(k\)个数的方案数，设\(c\)为当前列的编号，\(s_i\)为第\(i\)行的和

\[f_{i,j,k}=f_{i-1,j,k}+a_{i,c}\times f_{i-1,j-1,k}+(s_i-a_{i,c})\times f_{i-1,j,k-1} \]

即考虑第\(i\)行有没有选，以及是否选在了第\(c\)列

不合法的方案总数为

\[\sum_{j<k}f_{n,j,k} \]

但是这样枚举是\(O(mn^3)\)的，无法通过此题，发现其实并不需要知道\(j\)和\(k\)的具体数值，只需要知道相对大小关系即可

重新设计状态，设\(f_{i,j}\)表示前\(i\)行，当前列比其他列多选了\(j\)个的方案数

\[f_{i,j}=f_{i-1,j}+a_{i,c}\times f_{i-1,j-1}+(s_i-a_{i,c})\times f_{i-1,j+1} \]

这样复杂度变为了\(O(mn^2)\)

然后计算总方案数，设\(g_{i,j}\)表示前\(i\)行共选了\(j\)个数的方案数

\[g_{i,j}=g_{i-1,j}+s_i\times g_{i-1,j-1} \]

复杂度\(O(n^2)\)，总复杂度\(O(mn^2)\)

P3349 [ZJOI2016]小星星

题意简化：给定一棵树和一张图，给树上的点编号，保证编号是\(1\)到\(n\)的排列，并且对于树上的每一条边\((u,v)\)都能再图上找到对应的边求编号的方案数

先考虑朴素的dp，设\(f_{i,j,S}\)表示\(i\)的编号为\(j\)，且\(i\)的子树的编号集合为\(S\)的方案数，转移方程为

\[f_{i,j,k}=\prod_{p\in son}\sum_{(q,j)\in Edge}\sum_{l\subseteq k}f_{p,q,l} \]

这样转移的复杂度是\(O(3^nn^3)\)，显然无法通过

发现枚举子集的复杂度是十分巨大的，而不去枚举子集就无法满足\(1\)到\(n\)的排列的限制，考虑先不考虑这个限制，在减去不合法的方案

设\(f_{i,j}\)表示\(i\)的编号为\(j\)的方案数，转移方程为

\[f_{i,j}=\prod_{p\in son}\sum_{(q,j)\in Edge}f_{p,q} \]

考虑如何计算不合法的方案数，根据鸽笼原理，\(n\)个点的编号在\(1\)到\(n-1\)的范围里，至少会有两个点编号相同

所以可以用至少\(0\)个点编号相同的方案数\(-\)至少\(2\)个点编号相同的方案数\(+\)至少\(3\)个点编号相同的方案数\(-\)至少\(4\)个点编号相同的方案数······

枚举\(S\)的所有子集，对于每个子集dp一次，复杂度\(O(2^nn^3)\)

P3813 [FJOI2017]矩阵填数

先把每个格子分开考虑，一个格子能填的数的值域为\([1,\min(v_i,m)]\)，其中\(v_i\)为该格子所在的子矩阵

如果两个最大值不同的格子取到各自的最大值，那么它们满足的子矩阵一定是不同的，所以不同值域的格子互不影响

那么可以分值域考虑

设\(S_k\)表示最大值为\(k\)的格子的集合，则总方案数为\(k^{|S_k|}\)

\(|S_k|=v\)值等于\(k\)的子矩阵的面积并\(\cup v\)值小于\(k\)的子矩阵的面积并\(-v\)值小于\(k\)的子矩阵的面积并

现在要减去不合法的方案数，即某些子矩阵没有满足要求的方案数

考虑容斥

设\(T_{k,i}\)表示集合\(S_k\)中属于\(i\)号子矩阵的格子的集合，不合法的方案数为\((k-1)^{|T_{k,i}|}k^{|S_k|-|T_{k,i}|}\)

先减去\(1\)号子矩阵不满足要求的方案数、\(2\)号子矩阵不满足要求的方案数······，然后加上\(1,2\)同时不满足的方案数，\(2,3\)同时不满足的方案数，\(1,3\)同时不满足的方案数······，减去\(1,2,3\)同时不满足的方案数······

枚举\(v\)值相同的子矩阵集合的子集计算\(|T|\)，然后根据集合大小计算容斥系数即可

P3158 [CQOI2011]放棋子

设\(f[k][i][j]\)表示前k种颜色的棋子占领了任意i行j列的方案数，转移方程为

\[f[k][i][j]=\sum_{l=1}^{i-1}\sum_{r=1}^{j-1}f[k-1][l][r]\times g[a[k]][i-l][j-r]\times C_{n-i}^{i-l}\times C_{m-r}^{j-r}((i-l)\times (j-r)\ge a[k]) \]

\(g[k][i][j]\)表示用k个同色棋子占领任意i行j列的方案数

\[g[k][i][j]= C_{i \times j}^{k} - \sum_{l = 1}^i \sum_{r = 1}^j g[k][l][r] \times C_i^l \times C_j^r(l<i||r<j,i\times j\ge k) \]

因为不需要占领所有的行和列，所以最后的答案为\(\sum_{i=1}^n\sum_{j=1}^m f[c][i][j]\)

P2467 [SDOI2010]地精部落

题意简化：求\(1\)到\(n\)的排列中波动序列的个数

波动序列有两个重要性质

1. 对于一个波动序列，若\(i\)和\(i+1\)不相邻，交换它们后序列仍然是波动序列

2. 对于一个波动序列，将所有元素变为\(n-a_i+1\)后仍然是波动序列

设\(f_{i,j}\)表示长度为\(i\)的波动序列，第一个元素为\(j\)且\(j\)为波峰的方案数，考虑\(j\)和\(j-1\)的位置关系

• 若\(j\)和\(j-1\)不相邻，由性质\(1\)得，开头为\(j\)和开头\(j-1\)的波动序列是一一对应的，所以\(f_{i,j}+=f_{i,j-1}\)

• 若\(j\)和\(j-1\)相邻，\(j\)为波峰，那么\(j-1\)就为波谷，由性质\(2\)得，波谷为\(j-1\)的长度为\(i-1\)的波动序列和波峰为\(i-j+1\)的长度为\(i-1\)的波动序列是一一对应的，所以\(f_{i,j}+=f_{i-1,i-j+1}\)

总的DP转移方程为

\[f_{i,j}=f_{i-1,n-j+1}+f_{i,j-1} \]

P4104 [HEOI2014]平衡

根据杠杆平衡条件，\(F_1l_1=F_2l_2\)，即左侧橡皮到支点的距离和等于右侧橡皮到支点的距离和

将刻度线从左到右标号\(1\)到\(2n+1\)，即满足\(i\times (n+1)-sum_1=sum_2-(k-i)\times (n+1)\)

移项得\(sum1+sum2=k\times (n+1)\)

现在问题转化为将\(k\times (n+1)\)拆分为\(k\)个\(1\)到\(2n+1\)内的不相等的数

设\(f_{i,j}\)表示用\(i\)个数来拆分\(j\)的方案数，考虑如何通过一个已有数列得到一个新的数列，分两种情况讨论

• 若最小值不为\(1\)，虽然不确定原数列最小值是不是\(1\)，但是给原数列的每个数加上\(1\)一定是满足要求的，且新数列和原数列是一一对应的，所以\(f_{i,j}+=f_{i,j-i}\)

• 若最小值为\(1\)，可以先给原数列每个数都加上一，再添加一个\(1\)，这样的新数列和原数列也是一一对应的，所以\(f_{i,j}+=f_{i-1,j-i}\)

总的dp转移方程为\(f_{i,j}=f_{i-1,j-i}+f_{i,j-i}\)

P4253 [SCOI2015]小凸玩密室

设\(f[i][j]\)表示点亮\(i\)之后回到\(i\)的第\(j\)个祖先的最小花费

设\(g[i][j]\)表示点亮\(i\)之后回到\(i\)的第\(j\)个祖先的另一个儿子的最小花费

先更新\(g\)

1. 若\(i\)为叶子\(g[i][j]=(dis[i][j]+dis[brother(i,j)][1])\times w[brother(i,j)]\)

2. 若\(i\)只有左儿子\(g[i][j]=dis[ls[i]][1]\times w[ls[i]]+g[ls[i]][j+1]\)

3. 若\(i\)两个儿子都有\(g[i][j]=\min(dis[ls[i]][1]\times w[ls[i]]+g[ls[i]][1]+g[rs[i]][j+1],dis[rs[i]][1]\times w[rs[i]]+g[rs[i]][1]+g[ls[i]][j+1])\)

再更新\(f\)

1. 若\(i\)为叶子\(f[i][j]=dis[i][j]\times w[fa[i]]\)

2. 若\(i\)只有左儿子\(f[i][j]=f[ls[i]][j+1]+dis[ls[i]][1]\times w[ls[i]]\)

3. 若\(i\)两个儿子都有\(f[i][j]=\min(dis[ls[i]][1]\times w[ls[i]]+g[ls[i]][1]+f[rs[i]][j+1],dis[rs[i]][1]\times w[rs[i]]+g[rs[i]][1]+f[ls[i]][j+1])\)

最后统计答案时枚举起点，然后按照点亮的顺序统计即可

CF1557D Ezzat and Grid

先将区间离散化，考虑朴素的dp，题目中要求删掉的最少行数，可以转化为留下的最大行数，所以设\(f_i\)表示前\(i\)行最多留下几行，转移方程为

\[f_i=\max_{j=1}^{i-1}f_j\times g_{i,j}+1 \]

\(g_{i,j}\)表示第\(i\)行与第\(j\)行是否有相同的一列被涂黑，dp的复杂度为\(O(n)\)，但预处理\(g\)数组的复杂度为\(O(n^3)\)

考虑用线段树优化dp

线段树下标为\(i\)的地方维护的是所有第\(i\)列被涂黑的行的\(f\)的最大值，转移时在当前行被涂黑的下标的区间查询最大值，转移完一行后再更新线段树中的值

标签：方案,frac,sum,练习,矩阵,times,DP,dp
From： https://www.cnblogs.com/imyhy/p/17716113.html