题意：就是问你数组中长度为m的上升子序列(没说连续）有多少个。
1：可以想到状态表示dp[ i ][ j ] 代表以 a[i] 为结尾的且长度为 j 的严格单增子序列的数目，
那么状态计算就为
,
那我们如果不优化直接写，一层n，一层 j 一层 k ，肯定会超时
2:考虑进行优化：
① 既然要优化求前缀和的速度，不妨对 dp[1∼n][1] 构造一个树状数组，对 dp[1∼n][2] 构造一个树状数组，⋯，对 dp[1∼n][m] 构造一个树状数组。这样一来，我要求 dp[i][j]。就可以再dp[1~n][j-1]z这颗树状数组里求前缀和了，这样一个前缀和就可以在 O(logn) 时间内完成。总时间复杂度变为 O(n2logn)。
②再想我们用树状数组数组时要以a[i]大小为下标，故要离散化一下
#include using namespace std;#define pi acos(-1)#define xx first#define yy second#define endl "\n"#define lowbit(x) x & (-x)#define int long long#define ull unsigned long long#define pb push_backtypedef pair PII;typedef pair PDD;#define max(a, b) (((a) > (b)) ? (a) : (b))#define min(a, b) (((a) < (b)) ? (a) : (b))#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);const int N = 5e5 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;const double eps = 1e-8;int n, m;int dp[M][M];int a[N], l[N];int cases;//dp[i][j]=sum(dp[k][j-1])(k<i,a[k] s;for (int i = 1; i <= n; i++)s.pb(a[i]);sort(s.begin(), s.end());s.erase(unique(s.begin(), s.end()), s.end());for (int i = 1; i > n >> m;for (int i = 1; i > a[i];Unique();for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (j == 1)add(l[i], 1, 1);elseadd(l[i], j, query(l[i] - 1, j - 1));}}cout << "Case #" << ++cases << ":" << query(n, m) <> T;while (T--)solve();return 0;}还有另一种写法，开一层树状数组即可acwing上由这个解析
#include using namespace std;#define pi acos(-1)#define xx first#define yy second#define endl "\n"#define lowbit(x) x & (-x)#define int long long#define ull unsigned long long#define pb push_backtypedef pair PII;typedef pair PDD;#define max(a, b) (((a) > (b)) ? (a) : (b))#define min(a, b) (((a) < (b)) ? (a) : (b))// cout << "Case #" << ++cases << ": ";#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;const double eps = 1e-8;int n, m;int f[M][M];//表示以a[i]为结尾，长度为j的上升子序列的数量int a[N], l[N], tr[N];int cases;void add(int x, int c){for (int i = x; i <= n; i += lowbit(i))tr[i] = (tr[i] + c) % mod;}int query(int x){int res = 0;for (int i = x; i; i -= lowbit(i))res = (res + tr[i]) % mod;return res;}void Unique() // 离散化{vector s;for (int i = 1; i <= n; i++)s.pb(a[i]);sort(s.begin(), s.end());s.erase(unique(s.begin(), s.end()), s.end());for (int i = 1; i <= n; i++){int x = lower_bound(s.begin(), s.end(), a[i]) - s.begin() + 1;l[i] = x;}}void solve(){cout << "Case #" << ++cases <> n >> m;for (int i = 1; i > a[i];Unique();for (int i = 1; i <= n; i++) // 初始化第一层f[i][1] = 1;for (int j = 2; j <= m; j++) // 第一层已经算完了,我们改变循环的顺序，就可以只保留一棵树即可，为啥这样循环可以只开一棵树/*就在这做个解释吧，假设a[4]={20,30,40,10};离散化后大小为l[4]={2,3,4,1},f[1][1]=1;f[2][1]=1;初始化; 然后j=2这一层来说，首先清空tr数组，开始循环 f[3][1]=1;i=1; f[1][2]可以由谁来转移呢，显然没有那就是0f[4][1]=1;然后我们在l[1]这个位置上加上f[1][1],为下面得第二轮循环做准备i=2; f[2][2]可以由谁来转移呢，显然没有那就是f[1][1]的数量,前提a[1]l[1],得以转移， 然后我们在l[2]这个位置上加上f[2][1],为下面得第三轮循环做准备i=3;f[3][2]可以由谁来转移呢，显然没有那就是f[2][1]加上f[1][1]的数量,恰好我们前两轮都在相应得位置加上了，那么我们只需询问l[1],l[2]是否小于l[3]就可以了，如果小于直接树状数组前缀和就把f[2][1]和f[1][1]加上了，然后我们在l[3]这个位置上加上f[3][1],为下面得第三轮循环做准备依次类推，可以看出我们的状态转移只会用到上一层，而我们这样先枚举j，正好解决了开m颗树的问题*/{for (int i = 1; i <= n; i++)tr[i] = 0;for (int i = 1; i <= n; i++){f[i][j] = query(l[i] - 1); // 查询小于l[i]的个数(我们把a[i]的值离散化为l[i]了，但是a[i]之间的大小关系并未发生改变)add(l[i], f[i][j - 1]);// f[i][j]表示以a[i]结尾,长度为j的递增序列数量}}int res = 0;for (int i = 1; i <= n; i++)res = (res + f[i][m]) % mod;cout << res <> T;while (T--)solve();return 0;}