首页 > 代码库 > 51NOD 1376 最长递增子序列的数量 dp+BIT

51NOD 1376 最长递增子序列的数量 dp+BIT

题目链接:点这里!!

题意:中文题

题解:

  f[i]:iLIS,LIS 
  转,f[i].first=max{f[j].first}+1,j<ia[j]<a[i] 
  f[i].second=jf[j].second,f[j].first=f[i].first1 
  我BIT,i

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 5e5+10, M = 1e3+20,inf = 2e9,mod = 1e9+7;pii C[N];int n,a[N],b[N];int mx = 0;void update(int x,pii ret) {    for(int i = x; i <= n; i += i & (-i)) {       if(ret.first > C[i].first) {            C[i] = ret;        }        else if(ret.first == C[i].first){            C[i].second += ret.second;            C[i].second %= mod;        }    }}pii ask(int x) {    pii  ret = MP(0,1);    for(int i = x; i; i -= i & (-i))    {        if(C[i].first > ret.first) {            ret = MP(C[i].first,C[i].second);        }        else if(C[i].first == ret.first) {            ret.second += C[i].second;            ret.second %= mod;        }    }    return ret;}int main() {    scanf("%d",&n);    for(int i = 1; i <= n; ++i) {        scanf("%d",&a[i]);        b[i] = a[i];    }    sort(b+1,b+n+1);    int c = unique(b+1,b+n+1) - b - 1;    for(int i = 1; i <= n; ++i) {        a[i] = lower_bound(b+1,b+c+1,a[i]) - b;    }    int ans = 0;    for(int i = 1; i <= n; ++i) {        pii ret = ask(a[i]-1);        ret.first++;        if(ret.first > mx) {            mx = ret.first;            ans = ret.second;        }        else if(mx == ret.first) {            ans = (ans + ret.second) % mod;        }        update(a[i],ret);    }    cout<<ans<<endl;    return 0;}

 

51NOD 1376 最长递增子序列的数量 dp+BIT