2 3 2 1 2 3 3 2 3 2 1
Sample Output
Case #1: 3
Case #2: 0
题意：给你n,m,n个数，让你找出长度为m的最长上升序列。
题解：我们先按照一般思路想：dp[i][j]表示长度j以a[i]结尾的上升子序列长度。
显然这个复杂度是n^3的，我们可以用树状数组优化一层遍历变为n^2*logn在这之前先对a离散化。
扫描一遍的同时，将a[j]的信息更新到树上，那么扫描就可以用 logn时间统计出k的信息.
///1085422276 #include<bits/stdc++.h> using namespace std ; typedef long long ll; #define mem(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,127,sizeof(a)); #define inf 1000000007 #define mod 1000000007 inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)f=-1;ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=x*10+ch-‘0‘;ch=getchar(); }return x*f; } //************************************************ const int maxn=1000+5; int sum[maxn][maxn],a[maxn],b[maxn],n,m; int getsum(int k,int x){ int ans=0; while(x>0){ ans=(ans+sum[k][x])%mod; x-=(x&-x); } return ans; } void update(int k,int x,int pos){ while(x<maxn){ sum[k][x]=(sum[k][x]+pos)%mod; x+=(x&-x); } } int main(){ int oo=1; int T=read(); while(T--){ scanf("%d%d",&n,&m); for (int i = 1; i <= n; i++){ scanf("%d",&a[i]); b[i]=a[i]; } mem(sum); sort(b + 1, b + 1 + n); for(int i=1;i<=n;i++) a[i]=lower_bound(b + 1, b + 1 + n, a[i]) - b+1; update(0,1,1); int ans=0,k; for(int i=1;i<=n;i++){ for(ans=0,k=0;k<m;k++){ ans=getsum(k,a[i]-1); if(ans==0)break; update(k+1,a[i],ans); } } printf("Case #%d: ",oo++); cout<<(getsum(m,n+1)+mod)%mod<<endl; } return 0; }
2015南阳CCPC C - The Battle of Chibi DP树状数组优化
原文：http://www.cnblogs.com/zxhl/p/4924236.html