AcWing 297. 赤壁之战

题目链接：

很容易想到一个dp：表示长度为，以结尾的上升子序列的个数
转移的话就是从到枚举一个表示长度，再从到枚举一个，再从到枚举一个
转移就是如果，表示可以接在后面，那么
复杂度，可以过这个的
显然不是正解，那么我们需要优化掉一层枚举
对于最后一层从到，其实就是对的一个求和，可以树状数组求
所以说这是一个数据结构优化dp
不是正解：

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n, a[A], b[A], f[A][A], T, m;

int main(int argc, char const *argv[]) {
  cin >> T;
  for (int cas = 1; cas <= T; cas++) {
    memset(f, 0, sizeof f);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b + 1;
    for (int i = 1; i <= n; i++) f[1][i] = 1;
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++)
        for (int k = 1; k < j; k++)
            if (a[k] < a[j]) f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + f[m][i]) % mod;
    printf("Case #%d: %d\n", cas, ans);
  }
}

加了树状数组：

#include <bits/stdc++.h>
#define

using namespace std;
const int mod = 1e9 + 7;
int n, a[A], b[A], f[A][A], T, m, t[A];
int lowbit(int x) {return x & -x;}
void add(int x, int val) {while (x <= n) t[x] = (t[x] + val) % mod, x += lowbit(x);}
int ask(int x, int ans = 0) {
  while (x) ans = (ans + t[x]) % mod, x -= lowbit(x);
  return ans;
}

int main(int argc, char const *argv[]) {
  cin >> T;
  for (int cas = 1; cas <= T; cas++) {
    memset(f, 0, sizeof f);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b + 1;
    for (int i = 1; i <= n; i++) f[1][i] = 1;
    for (int i = 1; i <= m; i++) {
      memset(t, 0, sizeof t);
      if (i == 1) add(1, 1);
      for (int j = 1; j <= n; j++) f[i][j] = ask(a[j] - 1), add(a[j], f[i - 1][j]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + f[m][i]) % mod;
    printf("Case #%d: %d\n", cas, ans);
  }
}