p.s. 今天观察队友发现 , 队友在比赛的时候可以长时间保持有发散性的思考 , 这点应该注意 !
-
序列动态规划
不考虑容斥的做法 , 从暴力起手 .
设 \(dp_{i,j,0/1}\) , 代表进行到第 \(i\) 位 , 这个位置的值是 \(0/1\) , 上一个与之不同的位置在 \(j\) 的方案数 .
朴素的进行转移 , 用双指针将非法的区间归零即可 .
目前的时间复杂度是 \(O(k^2)\) 的 , 套路地考虑离散化 .
先抛去细节 , 考虑状态的变化 , 设 \(dp_{i,j,0/1}\) 代表进行到第 \(i\) 个关键点 , 上一个与之不同的位置在 \(lsh_{j-1}+1,lsh_{j}\) . 其中 \(lsh\) 是离散化映射数组 .
特别的 , \(dp_{i,i,0/1}\) 则代表在 \(lsh_{i-1}+1,lsh_{i}-1\) 不同.
这样的话直接转移就可以做到 \(O((n+m)^2)\) .
最重要的是如何选取关键点 , 才能在删除非法区间时保留信息 .
首先 \(0,k\) 是肯定要放的 .
考虑删除的过程 , 删除 \(j<l\) 的所有状态 , 但是考虑到 \(lsh_{j-1}+1,lsh_{j}\) 这里的设计 , 存在一种情况 ,不同的是 \(j\) 之前的数而不是 \(j\) 本身 , 所以 \(lsh_j -1\) 也应该加入关键点 , 参与离散化 .
现在最不熟悉的工作已经完成了 . 考虑优化 .
先把动态规划方程搬上来 ,
dp[0][i + 1][j] = A(dp[0][i + 1][j], dp[0][i][j]); dp[1][i + 1][j] = A(dp[1][i + 1][j], dp[1][i][j]); dp[0][i + 1][i] = A(dp[0][i + 1][i], dp[1][i][j]); dp[1][i + 1][i] = A(dp[1][i + 1][i], dp[0][i][j]); dp[0][i + 1][i + 1] = A(dp[0][i + 1][i + 1], M(A(P(2, Num[i + 1] - Num[i] - 1), S(1ll)), dp[0][i][j])); dp[0][i + 1][i + 1] = A(dp[0][i + 1][i + 1], M(A(P(2, Num[i + 1] - Num[i] - 1), S(1ll)), dp[1][i][j])); dp[1][i + 1][i + 1] = A(dp[1][i + 1][i + 1], M(A(P(2, Num[i + 1] - Num[i] - 1), S(1ll)), dp[0][i][j])); dp[1][i + 1][i + 1] = A(dp[1][i + 1][i + 1], M(A(P(2, Num[i + 1] - Num[i] - 1), S(1ll)), dp[1][i][j]));其实不难发现后六条都是一个全局和就可以搞定的事 .