本文共 1002 字，大约阅读时间需要 3 分钟。

详细解释点击：

离散化  ++++ dp思想

#include
   
    #include
    
     #include
     
      using namespace std;const int mod = 1000000007;int a[100010];int n;struct node{    int x,y;}s[100010];bool cmp(node p,node q){    if(p.x == q.x) return p.y < q.y;    return p.x < q.x;}int lowbit(int x){    return x&(-x);}void add(int pos,int num){    while(pos <= n)    {        a[pos] = (a[pos] + num) % mod;        pos += lowbit(pos);    }}int getsum(int pos){    int res = 0;    while(pos > 0)    {        res = (res + a[pos]) % mod;        pos -= lowbit(pos);    }    return res;}int main(){    while(scanf("%d",&n)!=EOF)    {        memset(a,0,sizeof(a));        memset(s,0,sizeof(s));        for(int i = 1;i <= n;i++)        {            scanf("%d",&s[i].x);            s[i].y = i;        }        sort(s+1,s+n+1,cmp);        int temp = 0;        for(int i = 1;i <= n;i++)        {            temp = getsum(s[i].y) + 1;            temp %= mod;            add(s[i].y,temp);        }        printf("%d\n",getsum(n));    }}
     
    
   

转载地址：http://eysgi.baihongyu.com/