【题意】求一个序列中LCS的数量?
【解题方法1】f[i]:以第i个数结尾的LCS的长度,和该长度的LIS的数量,转移的话,显然f[i].first=max(f[j].first)+1,j<i&&a[j]<a[i]。f[i].second=sum(f[j].second,f[j].first=f[i].first-1),我们可以用树状数组来优化这个转移,维护<=i的最大长度和数量。
【AC代码】
//51nod
//LCS CDQ/BIT
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
int a[maxn],n,cnt;
vector<int>vv;
typedef pair<int,int>P;//第一维表示长度,第二维表示数量
void getMax(P &x,P y)
{
if(x.first<y.first) x=y;
else if(x.first==y.first){
if((x.second+=y.second)>=mod){
x.second-=mod;
}
}
}
//P c[maxn];
//int lowbit(int i){
// return (i&(-i));
//}
//void init(){
// for(int i=1; i<=cnt; i++) c[i]=make_pair(0,0);
//}
//void add(int i,P v){
// while(i<=cnt){
// getMax(c[i],v);
// i+=lowbit(i);
// }
//}
//P getsum(int i){
// P ret=make_pair(0,1);
// while(i>0){
// getMax(ret,c[i]);
// i-=lowbit(i);
// }
// return ret;
//}
struct BIT {
int n; P b[maxn];
void init(int _n) {
n = _n;
for(int i = 1; i <= n; ++i) b[i] = P(0, 0);
}
void add(int i, P v) {
for(; i <= n; i += i & -i) getMax(b[i], v);
}
P sum(int i) {
P ret(0, 1);
for(; i>0; i -= i & -i) getMax(ret, b[i]);
return ret;
}
} bit;
int main()
{
scanf("%d",&n);
vv.clear();
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
vv.push_back(a[i]);
}
sort(vv.begin(),vv.end());
vv.resize(unique(vv.begin(),vv.end())-vv.begin());
bit.init(vv.size());
P ans=make_pair(0,0);
for(int i=1; i<=n; i++){
int pos=lower_bound(vv.begin(),vv.end(),a[i])-vv.begin()+1;
P now=bit.sum(pos-1);
++now.first;
getMax(ans,now);
bit.add(pos,now);
}
printf("%d\n",ans.second);
}
【解题方法2】 CDQ 点击打开链接参考知乎这一篇文章。
其实这是一个二维偏序问题,一维下标,二维是值,那么我们可以用cdq分治来做,具体做法如文章所示。
【AC 代码】
//51nod
//CDQ
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10,mod=1e9+7;
typedef pair<int,int>P;
P f[maxn];//first length,second count
void getMax(P &x,P y){
if(x.first<y.first) x=y;
else if(x.first==y.first){
if((x.second+=y.second)>=mod){
x.second-=mod;
}
}
}
int a[maxn],id[maxn];
bool cmp(int x,int y)
{
if(a[x]!=a[y]) return a[x]<a[y];
return x>y;
}
void cdq(int l,int r)
{
if(l==r) return ;
int m=(l+r)/2;
cdq(l,m);
for(int i=l; i<=r; i++) id[i]=i;
sort(id+l,id+r+1,cmp);
P mx=make_pair(0,0);
for(int i=l; i<=r; i++){
int idx=id[i];
if(idx<=m) getMax(mx,f[idx]);
else{
P now=mx;
now.first++;
getMax(f[idx],now);
}
}
cdq(m+1,r);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
for(int i=1; i<=n; i++){
f[i]=make_pair(1,1);
}
cdq(1,n);
P ans=make_pair(0,0);
for(int i=1; i<=n; i++){
getMax(ans,f[i]);
}
printf("%d\n",ans.second);
}
【解题方法3】