[agc009c]Division into Two前言题目大意DP

83 阅读 0 评论 55 点赞

我是靠谱客的博主寂寞香菇，最近开发中收集的这篇文章主要介绍[agc009c]Division into Two前言题目大意DP，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

DP题，还可以，不是很难。

题目大意

把一堆互不相同的数分成两个集合X和Y，其中一个集合X任意两数之差不小于A，另一集合Y任意两数之差不小于B。
问方案数，集合可以为空。

DP

把这些数排序。
接着添加第0个数无穷小以及第n+1个数无穷大。
我们假设A>=B。
设f[i]表示分配好了前i个数，第i个数去X集合的方案。
转移显然要找到上一个位置j。
第一种情况j=i-1，只要a[i]-a[i-1]>=A就能转移。
其余情况，首先a[i]-a[j]>=A，容易发现可以维护一个指针来维护最大的j。
其次可以维护一个指针k表示(k,i)这一段可以全部分到Y集合。
那么可以得到转移区间。
当然仍然还有一些要考虑，比如上一个X两边的Y。
首先因为A>=B，因此上一个X左边的如果无法选入Y，一定也不能选入X，因此我们只需要判断能否选入Y。
对于左右无法同时选入Y的决策j，即a[j+1]-a[j-1]

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100000+10,mo=1000000007;
ll a[maxn],A,B;
int tree[maxn*4],f[maxn];
int i,j,k,l,r,t,n,m,ans;
void change(int p,int l,int r,int a,int b){
    if (l==r){
        (tree[p]+=b)%=mo;
        return;
    }
    int mid=(l+r)/2;
    if (a<=mid) change(p*2,l,mid,a,b);else change(p*2+1,mid+1,r,a,b);
    tree[p]=(tree[p*2]+tree[p*2+1])%mo;
}
int query(int p,int l,int r,int a,int b){
    if (a>b) return 0;
    if (l==a&&r==b) return tree[p];
    int mid=(l+r)/2;
    if (b<=mid) return query(p*2,l,mid,a,b);
    else if (a>mid) return query(p*2+1,mid+1,r,a,b);
    else return (query(p*2,l,mid,a,mid)+query(p*2+1,mid+1,r,mid+1,b))%mo;
}
int main(){
    scanf("%d%lld%lld",&n,&A,&B);
    if (A<B) swap(A,B);
    fo(i,1,n) scanf("%lld",&a[i]);
    a[0]=-A;
    a[n+1]=a[n]+A;
    f[0]=1;
    change(1,0,n,0,f[0]);
    l=0;r=0;
    fo(i,1,n+1){
        while (a[i]-a[r+1]>=A) r++;
        if (i>=2&&a[i-1]-a[i-2]<B) l=i-2;
        if (a[i]-a[i-1]>=A) f[i]=f[i-1];
        (f[i]+=query(1,0,n,l,min(i-2,r)))%=mo;
        if (i<=n&&a[i+1]-a[i-1]>=B) change(1,0,n,i,f[i]);
    }
    ans=f[n+1];
    (ans+=mo)%=mo;
    printf("%dn",ans);
}