求给定序列中长度为M的上升子序列个数。$N,M<=1000$。
很容易想到方法。$f[i,j]$表示以第$i$个数结尾，长度为$j$的满足要求子序列个数。于是转移也就写出来了$f[i][j]+=f[k][j-1]$ $(k<i且A_k<A_i)$。边界$f[0][0]=1$。
然后这是$O(N^2 M)$的。考虑优化。每次由于只从$j-1$也就是上一层状态中选在自己序号之前且比自己小的数来转移，用时间保证第一个要求，第二个要求，将每个数离散化一下，用$m$层的BIT维护以离散化值为下标的$f$值前缀和，每次查$j-1$这一层比自己离散化值小的，然后再把自己的dp值加入j这一层即可。$O(NMlogn)$。卡着过去了。
没什么要说的了。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define lowbit(x) (x&(-x)) 8 #define dbg(x) cerr<<#x<<" = "<<x<<endl 9 using namespace std; 10 typedef long long ll; 11 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 12 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline T read(T&x){ 16 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 17 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 18 } 19 const int N=1000+7,P=1e9+7; 20 inline void inc(int&A,int B){A+=B;A>=P?A-=P:1;} 21 int T,n,m,tot; 22 struct BIT{ 23 int C[N]; 24 inline void clear(){for(register int i=0;i<=tot;++i)C[i]=0;} 25 inline void Update_add(int x,int val){while(x<=tot)inc(C[x],val),x+=lowbit(x);} 26 inline int Query_sum(int x){int ret=0;while(x>0)inc(ret,C[x]),x-=lowbit(x);return ret;} 27 }sum[N]; 28 int a[N],A[N],ans,tmp; 29 30 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 31 read(T);for(register int o=1;o<=T;++o){ 32 read(n),read(m);A[tot=1]=ans=0; 33 for(register int i=1;i<=n;++i)A[++tot]=read(a[i]); 34 sort(A+1,A+tot+1);tot=unique(A+1,A+tot+1)-A-1; 35 for(register int i=0;i<=m;++i)sum[i].clear(); 36 sum[0].Update_add(1,1); 37 for(register int i=1;i<=n;++i){ 38 int pos=lower_bound(A+1,A+tot+1,a[i])-A,tmp=0; 39 for(register int j=_min(i,m);j;--j){ 40 tmp=sum[j-1].Query_sum(pos-1); 41 sum[j].Update_add(pos,tmp); 42 if(j==m)inc(ans,tmp); 43 } 44 } 45 printf("Case #%d: %d ",o,ans); 46 } 47 return 0; 48 }