这里是三道题。
这场比赛的 B 题是本题的前置题，他告诉我们：
“假如当前区间右侧存在一个 \(k\)，使得我们再不往右走就无法占领 \(k\)，就向右走，否则向左。”是一种最优决策。
他甚至还慷慨地告诉我们：
最终的合法起始点集合要么为 \(x\in\bigcap\limits_{i=1}^n[i-a_i+1,i+a_i-1]\)，要么为 \(\emptyset\)。
有了这两个定论，我们就可以开始正解的思考了。
设 \(f_{i,j}\) 表示答案区间为 \([i,j]\) 的方案数。考虑容斥。设 \(g_{i,j,0/1}\) 表示我们现在区间已经拓宽到了 \([i,j]\)，下一步要向左或右走的方案数。则有：
\[g_{i,j,1}=(n-j+i)\times(g_{i+1,j,0}+g_{i,j-1,1})\]
\[g_{i,j,0}=(n-j+i)\times g_{i+1,j,0}+g_{i,j-1,1}\]
假如我们现在要求解 \(f_{l,r}\)，那么我们设初值 \(g_{l,r,0}=g_{l,r,1}=1\)，则有：
\[f_{l,r}=g_{1,n,0}\times\prod\limits_{i=l}^r(n-\max(i-l,r-i))\]
由于对于每一个 \(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)\)。
[code]#include#define ll long longusing namespace std;const int N=3005;int t,n,p,h[N],g[N][N][2],f[N][N],ans[N];void solve(){ cin>>n>>p,h[1]=1; for(int i=1;i |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
