前言
听说把枕头哭湿，晚上可以梦见大海
先说明一下情况。
我 \(\text{T2}\)，同样的数据，本地 \(\text{500ms}\to\) \(\text{sxyz: }1.7\texttt{s}\)。
\(\text{T3}, \text{CF 3s}\) 的时限，什么烂机子开 \(\text{1s}\)。
我们都有光明的未来。
我尽量克制住自己的情绪。
B / ABC176F
很智慧的一道题，稍微总结一下。
首先你显然有 \(dp_{i,j,k}\) 表示经过 \(i\) 次操作，前面剩下一个 \(j\) 一个 \(k\) 可以得到的最大分数。
暴力转移其实是比较简单的，假设这一次操作除了 \(j,k\) 另外三个数是 \(a,b,c\)。
-
把 \(a,b,c\) 删掉，\(dp_{i,j,k}=dp_{i-1,j,k}+[a=b=c]\)。
-
把 \(a,b,c\) 中的两个和 \(j,k\) 中的一个删掉，不妨设我们删的是 \(a,b,j\)，\(dp_{i,c,k}=dp_{i-1,j,k}+[a=b=j]\)。
-
把 \(a,b,c\) 中的一个和 \(j,k\) 删掉，不妨设我们删的是 \(a,j,k\)，\(dp_{i,b,c}=dp_{i-1,j,k}+[a=j=k]\)。
观察到第一种转移可以看作是全局加 \([a=b=c]\) 可以直接写一个全局增量标记在前面，最后答案直接 \(\text{ans}+\text{add}\) 即可。
至于后面两个，观察到变化的状态只有 \(\mathcal{O}(n)\) 个。并且变化一定是变大（因为有第一种转移的存在）
故你考虑把所有变化状态暴力取出来，然后维护一些最大值数组即可。
由于你每次只改变了那些会改变的，故总复杂度 \(\mathcal{O}(n^2)\)
很难崩的是，这个题你一旦常数大了一点你就会喜提 \(\text{TLE 95}\)。
标签：text,删掉,NOIP2024,dp,mathcal,赛后,模拟 From： https://www.cnblogs.com/SFsaltyfish/p/18440332