传送门
DP
十分显然的DP，但是不好写
设 f[ i ] 表示以第 i 个数作结尾时的方案数，原序列为 a
如果不考虑相同的序列：
那么转移就是 Σ f[ j ] （0< j < i && a [ j ] < a [ i ]）
复杂度为 O(n^2)
考虑优化：
先去重 ，得到数组 b
每次把f [ i ] 加到树状数组里 a [ i ]的值 在 b 中的位置 的位置
那么 f [ i ] 就等于 query(a [ i ] 的值在 b 中的位置-1) （query为树状数组的询问操作）
（上两行很重要，自己在脑子里想象一下，一定要理解原因）
然后考虑去掉相同的序列
很简单
只要每次更新完 f [ i ] 时把 f [ i ] 减去前面 a 中所有值为 a[ i ] 的位置（设为 j）
的 f[ j ]的和（还是要在脑子里想象一下...或者看代码来理解...）
最后注意要减去长度为 1 的方案数以及一些细节
代码其实不长
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> using namespace std; const int N=1e5+7; const int mo=1e9+7; int n,a[N],f[N],b[N],t[N],las[N],m,ans; //t是树状数组的数组,las[i]是前面a中所有值为a[i]的位置(设为j)的f[j]的和 inline int query(int x) { int res=0; while(x) { res=(res+t[x])%mo; x-=x&-x; } return res; } inline void add(int x,int v) { while(x<=m) { t[x]=(t[x]+v)%mo; x+=x&-x; } } int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1;//去重 for(int i=1;i<=n;i++) { int k=lower_bound(b+1,b+m+1,a[i])-b;//找到a[i]在b中的位置 f[i]=(f[i]+query(k-1)+1)%mo; f[i]-=las[k]; if(f[i]<0) f[i]+=mo; ans=(ans+f[i])%mo; add(k,f[i]); las[k]=(las[k]+f[i])%mo; } ans-=m; if(ans<0) ans+=mo;//减去长度为1的方案数 cout<<ans; return 0; }
