题意：
求n个数中长度为m的上升子序列的个数
解题思路：dp[i][j]表示第i个数长度为j的上升序列的个数。dp[i][j] = sum{dp[k][j-1] | a[k] < a[i]}，这里的时间复杂度有O(n³)，会超时，所以这里要有优化。其实可以将a[i]离散化，对于每一个j，构造一个树状数组，这样求sum{dp[k][j-1]}就可以用树状数组的求和了，时间复杂度可以降为O(n²logn)。
#include<iostream>#include<cstdio>#include<cstring>#include<set>#include<map>using namespace std;const int maxn = 1005;const int mod = 1e9+7;int n,m,dp[maxn][maxn];int a[maxn],tree[maxn][maxn];set<int> Set;map<int,int> Map;int lowbit(int x){return x & -x;}void add(int i,int j,int c){while(j <= n){tree[i][j] = (tree[i][j] + c) % mod;j += lowbit(j);}}int sum(int i,int j){int ans = 0;while(j > 0){ans = (ans + tree[i][j]) % mod;j -= lowbit(j);}return ans;}int main(){int t,cas = 1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);Set.clear();Map.clear();for(int i = 1; i <= n; i++){scanf("%d",&a[i]);Set.insert(a[i]);}int cnt = 0;for(set<int>::iterator it = Set.begin(); it != Set.end(); it++)Map[*it] = ++cnt;memset(dp,0,sizeof(dp));memset(tree,0,sizeof(tree));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){if(j == 1) dp[i][j] = 1;else dp[i][j] = (dp[i][j] + sum(j-1,Map[a[i]]-1)) % mod;add(j,Map[a[i]],dp[i][j]);}int ans = 0;for(int i = 1; i <= n; i++)ans = (ans + dp[i][m]) % mod;printf("Case #%d: %d\n",cas++,ans);}return 0;}
