四维DP?!
Blank
定义 $ dp[i][j][k][t] $ 代表填完前 $ t $ 个位置后, $ \begin{Bmatrix} 0,1,2,3 \end{Bmatrix} $ 这4个数字最后一次出现的位置,
排序后为 $ i,j,k,t ( i < j < k < t ) $ 的方案数目,则按照第 $ t+1 $ 位的数字的四种选择,可以得到四种转移。
对于限制可以按照限制区间的右端点分类,求出 $ dp [ i ] [ j ] [ k ] [ t ] $ 后,找到所有以 $ t $ 为区间右端点的限制条件,如果当前状态不满足所有限制条件则不合法,不再向后转移。
总时间复杂度 $ O(n^4) $ 。滚动一维,空间复杂度 $ O(n^3) $
UPD 一开始的模数为$10^9+7$,后来统一改成了$998244353$,但最后在polygon上生成数据的时候标程放错了,就跑出了模$10^9+7$的结果。对被这道题卡了的大佬们表示歉意!
1 |
|