题意：给定一个序列，找出长度为m的严格递增序列的个数。
思路：用dp[i][j]表示长度为i的序列以下标j结尾的总个数。三层for循环肯定超时，首先离散化，离散化之后就可以用树状数组来优化，快速查找下边在j之前，值比ary[j]小且长度为i-1 的个数
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1010; const int mod = 1000000007; int BIT[maxn]; int dp[maxn][maxn]; void add(int &a, int b) { a += b; while (a >= mod)//加法取模 a -= mod; } int lowbit(int x) { return x & (-x); } void update(int pos, int val, int n) { for (int i = pos; i <= n; i += lowbit(i)) add(BIT[i], val); } int query(int pos) { int ans = 0; for (int i = pos; i >= 1; i -= lowbit(i)) add(ans, BIT[i]); return ans; } int tmp[maxn]; int ary[maxn]; int main() { int n, m, T; int kase = 0; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &tmp[i]); ary[i] = tmp[i]; } //离散化 sort(tmp, tmp + n); int num = unique(tmp, tmp + n) - tmp; for (int i = 0; i < n; i++) ary[i] = lower_bound(tmp, tmp + num, ary[i]) - tmp + 1; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) dp[1][i] = 1;//初始化dp for (int i = 2; i <= m; i++) { memset(BIT, 0, sizeof(BIT));//每步都要初始化，因为只保存长度为i - 1的，每次只是快速查询而已。 for (int j = 0; j < n; j++) { dp[i][j] = query(ary[j] - 1);//找比他小的并且下标位置在他之前，长度为i - 1的 update(ary[j], dp[i - 1][j], n);//继续更新长度为i - 1的个数。 } } int ans = 0; for (int i = 0; i < n; i++) add(ans, dp[m][i]); printf("Case #%d: %d\n", ++kase, ans); } return 0; }