题目链接： /contest/390155#problem/M
题目大意：
给你一个长度为n的数组，问你这个数组中有多少种长度为m的递增序列，输出种类数。
思路：
这道题的状态转移方程很好想，我们用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示以第 j j j位的数结尾，递增序列长度为 i i i的种类数。
那么转移方程就可以写成：
d p [ i ] [ j ] = d p [ i ] [ j ] + d p [ i − 1 ] [ k ] , ( a [ k ] < a [ j ] ) dp[i][j]=dp[i][j]+dp[i-1][k],(a[k]<a[j]) dp[i][j]=dp[i][j]+dp[i−1][k],(a[k]<a[j])
/** @沉着，冷静！: 噗，这你都信！* @LastEditors: HANGNAG* @LastEditTime: -09-16 17:21:16* @FilePath: \ACM_vscode\DP\DP.cpp*/#include <algorithm>#include <iostream>#include <map>#include <math.h>#include <queue>#include <set>#include <stack>#include <stdio.h>#include <string.h>#include <string>#include <vector>#define emplace_back push_back#define pb push_backusing namespace std;typedef long long LL;const int mod = 1e9 + 7;const double eps = 1e-6;const int inf = 0x3f3f3f3f;const int N = 1e3 + 10;int dp[N][N];int a[N];int main(){int t;scanf("%d", &t);int tot = 1;while (t--){int n, m;memset(dp, 0, sizeof(dp));scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++){dp[i][1] = 1;}for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}for (int i = 2; i <= n; i++){for (int j = 2; j <= i; j++){for (int k = 1; k < i; k++){if (a[i] > a[k]){dp[i][j] += dp[k][j - 1];}dp[i][j] %= mod;}}}int ans = 0;for (int i = m; i <= n; i++){ans += dp[i][m];//printf("%d %d %d**\n", i, m, dp[i][m]);}ans %= mod;printf("Case #%d: %d\n", tot++, ans);}return 0;}
很显然这种朴素的写法的复杂度是 O ( n 3 ) O(n^3) O(n3)这道题过不了。
但是我们可以发现它每次加的都是比当前小的数的状态，那么我们可以把这个数组每个数的前缀记录，每次加上它的前缀。（如果现在判断到第j个数，那么我们先找到a[j]排第几个，假设排b[j]，这里的前缀是指把这个数组排序后，dp[i][j]就加上数组里到b[j]-1的前缀和）
这里我们要想实现对一个数组进行修改和前缀查询，可以用线段树和树状数组实现，（树状数组更简单一些）。因为这里a数组范围比较大，但是数量不多，所以我们可以离散化一下a数组。
AC代码：
/** @沉着，冷静！: 噗，这你都信！* @LastEditors: HANGNAG* @LastEditTime: -09-16 21:09:20* @FilePath: \ACM_vscode\DP\DP.cpp*/#include<algorithm>#include<string.h>#include<iostream>#include<stdio.h>#include<string>#include<math.h>#include<vector>#include<queue>#include<stack>#include<map>#include<set>#define emplace_back push_back#define pb push_backusing namespace std;typedef long long LL;const LL mod = 1e9 + 7;const double eps = 1e-6;const LL inf = 0x3f3f3f3f;const LL N = 1e3 + 10;LL dp[N][N];LL a[N], b[N], c[N];LL n, m;LL lowbit(LL x){return x & (-x);}LL sum(LL x){LL num = 0;while(x){num += c[x];num %= mod;x -= lowbit(x);}return num;}void add(LL x,LL y){while(x<=n){c[x] += y;c[x] %= mod;x+=lowbit(x);}}int main(){LL t;scanf("%lld", &t);LL tot = 1;while(t--){memset(dp, 0, sizeof(dp));scanf("%lld%lld", &n, &m);for (LL i = 1; i <=n;i++){scanf("%lld", &a[i]);b[i] = a[i];}sort(a + 1, a + 1 + n);for (LL i = 1; i <= n;i++){b[i] = lower_bound(a + 1, a + 1 + n, b[i]) - a+1;}dp[0][0] = 1;for (LL i = 1; i <= m;i++){memset(c, 0, sizeof(c));add(1, dp[i - 1][0]);for (LL j = 1; j <= n;j++){dp[i][j] = sum(b[j]-1);add(b[j], dp[i-1][j]);}}LL ans = 0;for (LL i = 1; i <= n;i++){ans += dp[m][i];ans %= mod;}printf("Case #%lld: %lld\n",tot++, ans);}return 0;}
