http://acm.hdu.edu.cn/showproblem.php?pid=2227&&树状数组+离散化+dp
http://acm.hdu.edu.cn/showproblem.php?pid=2227#include<iostream>#include<cstdio>#include<string.h>#include<algorithm>#define N 100005#define M1000000007using namespace std;typedef long long L;int kp;int a;int s;int n;int tot;inline int lowbit(int x){return x&(-x);}void update(int x,int v){ while(x<N){s+=v;if(s>=M)s%=M;x+=lowbit(x);}}L Quary(int x){L sum=0;while(x>0){ sum+=s;if(sum>=M)sum%=M;x-=lowbit(x);}return sum;}int lisan(int x){ int l=1,r=tot;while(l<=r){int mid=(l+r)>>1;if(a==x) return mid;else if(a>x) r=mid-1;else if(a<x) l=mid+1;}return -1;}int main(){while(~scanf("%d",&n)){ memset(s,0,sizeof(s));tot=0;for(int i=1;i<=n;++i){scanf("%d",&kp);a=kp;}sort(a+1,a+n+1);for(int i=1;i<=n;++i)if(i==1||(a!=a))a[++tot]=a;L res=0;for(int i=1;i<=n;++i){ int num=lisan(kp);L k=Quary(num);res+=k+1;if(res>=M)res%=M;update(num,k+1);}printf("%d\n",res);}return 0;}//这道题算是树状数组题中比较难的一个题，不但需要离散化思想还要有动态规划思想//首先说一下这一题的题意：给你一串数让你求其中有多少个非递减子串。这里用到树状数组//主要是用来统计第i个位置共找到多少个非递减子串。动态规划思想dp={sum......dp j<i,a<=a]}//dp=0+1;//dp=dp+1;//dp=dp+dp+1;//下面在说一下为什么要离散化，因为给定串中的数最大不超过2^31,这样不能进行树状数组的操作，因此需要把所有的数映射到1……n这个区间。。。
页:
[1]