P11126 [ROIR 2024] 三等分的数组 (Day 2)
考虑到数的选取与输入顺序无关，我们将数丢到桶里，记 \(c_x\) 为 \(x\) 出现的次数。
那么我们取出三元组的过程可以描述为下面二者之一：
- 选取 \(c\) 中的一个位置，将其减去 \(3\)。
- 选取 \(c\) 中连续的三个位置，将其减去 \(1\)。
令 \(f[x][i][j]\) 表示当前考虑到 \(c\) 中的第 \(x\) 位，第 \(x\) 位消去了 \(i\) 个，第 \(x-1\) 位消去了 \(j\) 个，\(x-2\) 及之前的位置全部消去的答案。
这样设状态是可以正确转移的，因为能消除第 \(x-2\) 位的最大位置就是 \(x\)，如果留到 \(x\) 之后就永远消不掉了。
我们可以枚举使用 \((x,x,x)\) 的次数 \(t\)，则剩下的 \((i-3t)\) 必须全部用于使用 \((x-2,x-1,x)\)，则有转移：
\[f[x][i][j]=\sum\limits_{t=0}^{\lfloor\frac{x}{3}\rfloor} f[x-1][j-(i-3t)][c_{x-2}-(i-3t)]
\]
酱紫会 T，考虑优化。
我们发现（可以归纳理解）：
\[\begin{aligned}
&\quad\sum\limits_{t=0}^{\lfloor\frac{x}{3}\rfloor} f[x-1][j-(i-3t)][c_{x-2}-(i-3t)]\\
&=f[x][i-3][j]+f[x][j-i][c_{x-2}-i]\\
\end{aligned}
\]
所以不需要枚举 \(t\)，状态转移优化到 \(O(1)\)。
考虑分析这样做的时间复杂度。
对于 \(f[x][i][j]\)，\(i,j\) 的上界是 \(c_x,c_{x-1}\)，所以总状态数是：
\[\sum\limits_{i=1}^m c_i c_{i-1}
\]
状态数是 $O(m^2)$ 的
\[\begin{aligned}
&\quad\sum\limits_{i=1}^m c_i c_{i-1}\\
&\le \sum\limits_{i=1}^m c_i^2&(\text{排序不等式})\\
&\le m^2
\end{aligned}
\]
状态数是 $O(n^2)$ 的
我们将 \(c\) 按下标的奇偶性两两分组：
\[A=c_1+c_3+c_5+\dots\\
B=c_2+c_4+c_6+\dots
\]
展开 \(A\times B\) 可知：
\[\sum\limits_{i=1}^m c_i c_{i-1}\le A\times B
\]
而 \(A+B=n\)，据均值不等式知 \(A\times B\le \frac{n^2}{4}\)。
所以原式是 \(O(n^2)\) 的。
所以时间复杂度是 \(O(m\times \min(n^2,m^2))\)，而且跑不满。
只是空间需要注意滚动数组。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=5e3+5,P=1e9+7;
int n,m,c[M],f[2][N][N];
signed main(){cin>>n>>m;m+=2;for(int i=1,x;i<=n;i++) cin>>x,x+=2,c[x]++;f[0][0][0]=1;for(int x=3,cur=1;x<=m;x++,cur^=1){for(int i=0;i<=c[x];i++){for(int j=0;j<=c[x-1];j++){if(i>=3) f[cur][i][j]=f[cur][i-3][j];else f[cur][i][j]=0;if(c[x-2]>=i&&j>=i) (f[cur][i][j]+=f[cur^1][j-i][c[x-2]-i])%=P;}}}cout<<f[m&1][c[m]][c[m-1]]<<"\n";return 0;
}