[DP记录]AT2292 [AGC009C] Division into Two

**题意** ： 给定 $n$ 个不同的整数，求将它们分成两个集合 $S_1,S_2$ ，并且 $S_1$ 集合中任意两个数的差 $\geq A$ ， $S_2$ 集合中任意两个数的差 $\geq B$ 的方案数。 答案对 $10^9+7$ 取模。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 记给出的整数集合为 $T$。 考虑如何检验一组方案是否合法。可以将 $S_1,S_2$ 分别排序后，查看相邻元素的差值是否均 $\geq A,B$。 因此，我们将 $T$ 从小到大排序（似乎本来就排序了），然后 $\rm DP$。 设 $dp[i][0/1]$ 表示将 $T_i$ 放入 $S_1$ 或 $S_2$ 的方案数。 转移时，枚举一整段划给 $S_1$ 或 $S_2$。 假设要将 $A_{[l,r]}$ 划给 $S_1$ ，则段内差值要 $\geq A$ ，且两端外侧的差值要 $\geq B$。 范围可以用双指针求解，转移贡献容易用部分和计算。 复杂度 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 100500 using namespace std; const int mod=1000000007; ll x[MaxN],dp[MaxN][2],t0,t1; int n; int main() { scanf("%d%lld%lld",&n,&t0,&t1); for (int i=2;i<=n+1;i++)scanf("%lld",&x[i]); x[1]=-1ll<<61;x[n+2]=1ll<<61; dp[1][0]=dp[1][1]=1; int l0=1,r0=0,l1=1,r1=0; for (int i=2;i<=n+1;i++){ if (x[i]-x[i-1]<t0)l0=i-1; if (x[i]-x[i-1]<t1)l1=i-1; while(r0<i-1&&x[i+1]-x[r0+1]>=t1)r0++; while(r1<i-1&&x[i+1]-x[r1+1]>=t0)r1++; dp[i][0]=((l0<=r0 ? dp[r0][1]-dp[l0-1][1] : 0)+dp[i-1][0])%mod; dp[i][1]=((l1<=r1 ? dp[r1][0]-dp[l1-1][0] : 0)+dp[i-1][1])%mod; }printf("%lld",(10ll*mod+dp[n+1][0]-dp[n][0]+dp[n+1][1]-dp[n][1])%mod); return 0; } ```