【AtCoder Grand Contest 009 C】Division into Two | Mrsrz's blog

动态规划。

题目大意：

给定 $n,A,B$ 和 $n$ 个整数 $s_1,s_2,s_3,\ldots,s_n$，要求把这 $n$ 个数划分为两个集合，满足第一个集合中的元素两两之差大于等于 $A$，第二个集合中的元素两两之差大于等于 $B$。

问有多少种不同的划分方法。

题解：

我们把 $s$ 从小到大排序，依次考虑。并且我们钦定 $A\leq B$。

首先判无解。如果存在 $i\in(1,n)$，有 $s_{i+1}-s_{i-1}\lt A$，那么无解（$s_{i-1},s_{i},s_{i+1}$ 不管怎么放都不能满足条件）。

然后考虑 dp。令 $f_{i,j}$ 表示前 $i$ 个数，最后一个放在第二个集合（限制条件为 $B$ 的那个）的数的位置为 $j$ 的方案数。

有以下情况：

• 数 $s_i$ 放在第一个集合（限制条件为 $A$ 的那个），且 $s_{i}-s_{i-1}\geq A$。则 $f_{i,j}=f_{i-1,j}$（$0\leq j\lt i$）。
• 数 $s_i$ 放在第一个集合（限制条件为 $A$ 的那个），但 $s_{i}-s_{i-1}\lt A$。则 $f_{i,j}=0$（$0\leq j\lt i-1$），$f_{i,i-1}=f_{i-1,i-1}$。
• 数 $s_i$ 放在第二个集合。则 $f_{i,i}=\sum_{s_i-s_j\geq B}f_{i-1,j}$。

可以直接用前缀和优化这个 dp。

时间复杂度 $O(n)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5,md=1e9+7;
LL A,B,s[N];
int n,h,dp[N];
inline void upd(int&a){a+=a>>31&md;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>A>>B;
    if(A>B)swap(A,B);
    for(int i=1;i<=n;++i)cin>>s[i];
    s[0]=-B;
    sort(s+1,s+n+1);
    for(int i=2;i<n;++i)
    if(s[i+1]-s[i-1]<A){
        cout.put('0');
        return 0;
    }
    h=0,dp[0]=1;
    for(int i=1,it=0;i<=n;++i){
        dp[i]=dp[i-1];
        while(s[it+1]+B<=s[i])++it;
        if(it>=h){
            upd(dp[i]+=dp[it]-md);
            if(h)upd(dp[i]-=dp[h-1]);
        }
        if(s[i]-s[i-1]<A)h=i-1;
    }
    upd(dp[n]-=dp[h-1]);
    cout<<dp[n]<<'\n';
    return 0;
}