PAT2019顶级7-2：美丽的序列（线段树+DP）

题意：

美丽的序列是指：序列中包含一对相邻元素，它们的差小于等于M。

现在给出一个序列，请你计算其中美丽的子序列的个数。

题解：

当初做的时候线段树基本功不扎实没有写出来。隔了三个月再看感觉挺简单的。

由于美丽的序列定义，可以发现美丽的序列实在是太多了，所以解法是反其道而行之，先求出不美丽的序列数量，用总序列数量减去不美丽的序列数量，就是答案。

那么怎么求出不美丽的序列数量呢？

我的做法是开一个dp数组，表示以当前元素结尾的不合法序列的数量。

然后我们从左到右遍历数组，可以推出状态转移方程：

dp的值 = 结尾元素的值和当前元素的值差大于M的子序列数量 + 1。因为它自己也算是一个不合法的子序列。

如何快速查询结尾元素的值在指定区间里的子序列数量呢？这里我调用了线段树维护，每次计算出当前dp值后在线段树里更新，具体见代码，感觉还是挺简单的。

这次千万不要出高难度的DP啊。。。多出数据结构，三维四维滚动数组真顶不住啊。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+14;
typedef long long ll;
const ll mod=1e9+7;
struct node {
    int l;
    int r;
    ll sum;
}segTree[maxn*5];
int a[maxn];
void build (int i,int l,int r) {
    segTree[i].l=l;
    segTree[i].r=r;
    if (l==r) {
        segTree[i].sum=0;
        return;
    }
    int mid=(l+r)>>1;
    build (i<<1,l,mid);
    build (i<<1|1,mid+1,r);

}
void add (int i,int t,ll b) {
    segTree[i].sum+=b;
    segTree[i].sum%=mod;
    if (segTree[i].l==t&&segTree[i].r==t) return;
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if (t<=mid) add (i<<1,t,b);
    else add (i<<1|1,t,b);
    segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum;
    segTree[i].sum%=mod;
}
ll query (int i,int l,int r) {
    if (l==segTree[i].l&&r==segTree[i].r) return segTree[i].sum%mod;
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if (r<=mid) return query(i<<1,l,r)%mod;
    else if (l>mid) return query(i<<1|1,l,r)%mod;
    else return query(i<<1,l,mid)%mod+query(i<<1|1,mid+1,r)%mod;
}
ll dp[maxn];
int main () {
    int N,M;
    ll ans=1;
    scanf("%d%d",&N,&M);
    //if (N==1e5) while(1);
    for (int i=1;i<=N;i++) scanf("%d",&a[i]),a[i]+=1e5;
    //printf("%lld
",ans);
    build(1,1,maxn);
    for (int i=1;i<=N;i++) {
        dp[i]=(query(1,1,a[i]-M-1)%mod+query(1,a[i]+M+1,maxn)%mod+1)%mod;
        //dp[i]%=mod;
        add(1,a[i],dp[i]);
    }
    ll tt=0;
    for (int i=1;i<=N;i++) tt+=dp[i],tt%=mod;
    for (int i=1;i<=N;i++) {
        ans<<=1;
        ans%=mod;
    }
    //tt%=mod;
    ans=ans+mod-(tt+1)%mod;
    ans%=mod;
    //ans=0;

    printf("%lld
",ans);
}

PAT2019顶级7-2：美丽的序列（线段树+DP）

相关推荐