程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3450 樹狀數組優化dp

hdu 3450 樹狀數組優化dp

編輯:C++入門知識

hdu 3450 樹狀數組優化dp


 

題意就不說了; hdu2227差不多只不過這道題不是遞增 而是相鄰差不超過d 其實是為都一樣, 也有差別;

這道題沒說范圍 並且樹之間的大小關系對結果有影響,所以樹狀數組裡根據原來id來求,由於數值很大 所以還是用到離散化 這裡的離散化感覺和映射差不多,離散化用來查找id;

當num【i】的id是x是,dp【i】表示方案數 很明顯dp【i】=sun(dp【j】,j

 

#include
#include
#include
#include
using namespace std;

#define mod 9901

int num1[100010],num2[100010],mark[100010],tt,n;
int coun[100010];
int update(int a,int b)
{
    for(int i=a;i<=n;i+=(i&-i))
    {
        coun[i]+=b;
        coun[i]%=mod;
    }
    return 0;
}
int find(int a)
{
    int s=0;
    for(int i=a;i>=1;i-=(i&-i))
    {
        s+=coun[i];
        s%=mod;
    }
    return s;
}
int searchr(int a)
{
    int left=1,right=tt,now;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(mark[mid]<=a)    
        {   
            now=mid;
            left=mid+1;
        }
        else 
        {
            right=mid-1;
        }
    }    
    return now;
}
int searchl(int a)
{
    int left=1,right=tt;
    while(left<right)
    { 
        int mid=(left+right)/2;
        if(mark[mid]<a) left=mid+1;
        else if(mark[mid]==a) return mid;
        else right=mid;
    }
    return left;
}
int main()
{
    int i,j,d;
    while(~scanf("%d%d",&n,&d))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num1[i]);
            num2[i]=num1[i];
        }
        sort(num2+1,num2+1+n);
        tt=0;         
        num2[0]=-1;
        for(i=1;i<=n;i++)
        {
            if(num2[i]!=num2[i-1])
            {
                tt++;
                mark[tt]=num2[i];
            }
        }
        memset(coun,0,sizeof(coun));
        int sum=0;
        int x=searchl(num1[1]);
        for(i=1;i<=n;i++)
        {
            int left=searchl(num1[i]-d)-1;
            int right=searchr(num1[i]+d);
            int now=searchl(num1[i]);
            int s=find(right)-find(left);
            s=(s%mod+mod)%mod;
            sum+=s;
            sum%=mod;
            update(now,s+1);
        }
        printf("%d\n",sum);
    }
    return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved