萌新看不懂题解求助
查看原帖
萌新看不懂题解求助
280800
lingfunny楼主2024/12/30 18:35

设 fi,jf_{i, j} 表示第 ii 行填 jj 后，前 ii 行贡献的最大值。我们不考虑初始填过的数之间产生的贡献。

设 ci,jc_{i, j} 表示第 ii 行中 jj 这个数的数量。为了美观，把 ci,−1c_{i, -1} 记作 cic_{i}。

我们有两个转移：

fi,j←fi−1,j+ci−1×ci,j+(ci−1+ci−1,j)×ci(这两行填相同数字)fi,j←fi−1,t+ci−1×ci,t+ci−1,j×ci(这两行填不同数字)\begin{align*} f_{i, j}&\gets f_{i-1,j} + c_{i-1} \times c_{i, j} + (c_{i-1} + c_{i-1, j}) \times c_{i}& (\text{这两行填相同数字})\\ f_{i, j}&\gets f_{i-1, t} + c_{i-1} \times c_{i, t} + c_{i-1, j} \times c_{i}&(\text{这两行填不同数字}) \end{align*}

确实，对于满足 ci−1,j=ci,j=0c_{i-1, j} = c_{i, j} = 0 的 jj，即第 ii 行和第 i−1i-1 行都没出现的数，有转移：

fi,j←fi−1,j+ci−1cifi,j←fi−1,t+ci−1×ci,t\begin{align*} f_{i, j} &\gets f_{i-1, j} + c_{i-1}c_{i}\\ f_{i, j} &\gets f_{i-1, t} + c_{i-1} \times c_{i, t} \end{align*}

如果记 a=ci−1cia = c_{i-1}c_i，b=max⁡1≤t≤k(fi−1,t+ci−1×ci,t)b = \max\limits_{1\le t\le k} \left(f_{i-1, t}+c_{i-1}\times c_{i, t}\right)，这些转移是 x←max⁡(x+a,b)x\gets \max(x + a, b)，可以用线段树维护 dp 值。

但是怎么快速求 bb 啊？

2024/12/30 18:35