【ybt】【数据结构 树状数组 课过 例3】严格上升子序列数

本文主要是介绍【ybt】【数据结构 树状数组 课过 例3】严格上升子序列数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

严格上升子序列数

题目链接：YbtOJ

---

解题思路

我们设 $f_{i,j}$ 表示以 $i$ 结尾，长度为 $j$ 的序列数。
如果直接暴力做，那是 $O(n^3)$ 的时间复杂度。
我们可以离散化，然后用树状数组维护每一种方案数的情况。
其实和逆序对挺像的说（无端感受）

code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define lb(x) (x&(-x))
#define int long long
using namespace std;const int mod=1e9+7;int T;
int n,m;
int c[1010][1010];
int f[1010][1010];struct abc{int a,b;
}a[100010];bool cmp(abc a,abc b)
{if(a.a!=b.a)return a.a<b.a;return a.b>b.b;
}void in(int x,int y,int z)
{for(;x<=n;x+=lb(x))c[x][y]=(c[x][y]+z)%mod;
}int fd(int x,int y)
{int s=0;for(;x;x-=lb(x))s=(s+c[x][y])%mod;return s;
}signed main()
{cin>>T;for(int h=1;h<=T;h++){memset(c,0,sizeof(c));memset(f,0,sizeof(f));cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",&a[i].a);a[i].b=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(j==1)f[i][j]=1;elsef[i][j]=fd(a[i].b-1,j-1);in(a[i].b,j,f[i][j]);}int ans=0;for(int i=m;i<=n;i++)ans=(ans+f[i][m])%mod;printf("Case #%lld: %lld\n",h,ans);}
}

这篇关于【ybt】【数据结构 树状数组 课过 例3】严格上升子序列数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---