首页 > 代码库 > hdu 3450(树状数组+dp)

hdu 3450(树状数组+dp)

2024-07-24 09:21:26   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3450

Counting Sequences

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 1815    Accepted Submission(s): 618


Problem Description
For a set of sequences of integers｛a1，a2，a3，...an｝, we define a sequence｛ai1,ai2,ai3...aik｝in which 1<=i1<i2<i3<...<ik<=n, as the sub-sequence of ｛a1，a2，a3，...an｝. It is quite obvious that a sequence with the length n has 2^n sub-sequences. And for a sub-sequence｛ai1,ai2,ai3...aik｝，if it matches the following qualities: k >= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.
 

Input
Multiple test cases The first line will contain 2 integers n, d（2<=n<=100000，1<=d=<=10000000） The second line n integers, representing the suquence
 

Output
The number of Perfect Sub-sequences mod 9901
 

Sample Input
4 2
1 3 7 5
 

Sample Output
4
 

Source
2010 ACM-ICPC Multi-University Training Contest（2）——Host by BUPT
 

Recommend
We have carefully selected several similar problems for you:  3030 1542 1255 2688 3449 
题意：一个集合有n个数，然后要你找出所有的完美子序列对9901取模~
思路：很容易想到dp,我们可以用dp[i]表示以第i个数为结尾的完美子序列的个数，那么sum(总的完美子序列的个数)=dp[2]+dp[3]+dp[4]+.....dp[n];
然后接着想满足完美子序列的条件是什么？ |x-a[i]|<=d  那么就有      a[i]-d <=x <=a[i]+d;
然后用树状数组动态维护即可~~~ 
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
const int N=1e5+100;
const int mod=9901;
using namespace std;


struct node
{
 int v,id;
}a[N];
bool cmp(node a,node b)
{
 return a.v<b.v;
}
int n,d,c[N],b[N];


int lowbit(int x)
{
  return x&(-x);
}

void update(int x,int d)
{
  while(x<=n)
  {
   c[x]+=d;
   if(c[x]>mod)c[x]%=mod;
   x+=lowbit(x);
  }
}

int getsum(int x)
{
  int ans=0;
  while(x>0)
  {
   ans+=c[x];
   if(ans>mod)ans%=mod;
   x-=lowbit(x);
  }
  return ans;
}

int find(int x)
{
  if(x>=a[n].v)return n;
  if(x<a[1].v)return 0;

  int l=1,r=n,ret=0;
  while(l<=r)
  {
   int mid=(l+r)/2;
   if(x>=a[mid].v)
    {
      ret=mid;
      l=mid+1;
    }
   else
    r=mid-1;
  }
  return ret;
}

int main()
{
        while(scanf("%d%d",&n,&d)!=EOF)
        {
          memset(c,0,sizeof(c));
          memset(b,0,sizeof(b));

          for(int i=1;i<=n;i++)
          {
            scanf("%d",&a[i].v);
            a[i].id=i;
          }
          sort(a+1,a+1+n,cmp);
          for(int i=1;i<=n;i++)b[a[i].id]=i;

          int sum=0;
          for(int i=1;i<=n;i++)
          {
            int p=find(a[b[i]].v+d);
            int q=find(a[b[i]].v-d-1);
            int temp=getsum(p)-getsum(q);
                temp=(temp+mod)%mod;
                sum=(sum+temp)%mod;
                update(b[i],temp+1);
          }
          printf("%d\n",sum);
        }
        return 0;
}


hdu 3450(树状数组+dp)


联系
我们