首页 > 代码库 > 51NOD 1376 最长递增子序列的数量 dp+BIT
51NOD 1376 最长递增子序列的数量 dp+BIT
题目链接:点这里!!
题意:中文题
题解:
f[i]:以第i个数结尾的LIS的长度,和该长度的LIS数量
转移的话,显然f[i].first=max{f[j].first}+1,j<i且a[j]<a[i]
f[i].second=∑jf[j].second,f[j].first=f[i].first−1
我们可以用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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。