[CF2018F] Speedbreaker Counting 题解
这里是三道题。这场比赛的 B 题是本题的前置题，他告诉我们：
“假如当前区间右侧存在一个 \(k\)，使得我们再不往右走就无法占领 \(k\)，就向右走，否则向左。”是一种最优决策。
他甚至还慷慨地告诉我们：
最终的合法起始点集合要么为 \(x\in\bigcap\limits_{i=1}^n\)，要么为 \(\emptyset\)。
有了这两个定论，我们就可以开始正解的思考了。
设 \(f_{i,j}\) 表示答案区间为 \(\) 的方案数。考虑容斥。设 \(g_{i,j,0/1}\) 表示我们现在区间已经拓宽到了 \(\)，下一步要向左或右走的方案数。则有：
\
\
假如我们现在要求解 \(f_{l,r}\)，那么我们设初值 \(g_{l,r,0}=g_{l,r,1}=1\)，则有：
\
由于对于每一个 \(f_{l,r}\) 都要跑一遍 \(O(n^2)\ dp\)，所以导致时间复杂度劣到了 \(O(n^4)\)，连 F2 都过不了，考虑优化。
考虑一些神奇的 trick。发现这些 \(dp\) 终点状态相同（\(g_{1,n,0}\)），转移方程相同，于是我们从 \(g_{1,n,0}\) 开始倒着推回去，就可以只用一次 \(dp\) 解决问题。时间复杂度 \(O(n^2)\)。
#include#define ll long longusing namespace std;const int N=3005;int t,n,p,h,g,f,ans;void solve(){ cin>>n>>p,h=1; for(int i=1;i
页:
[1]