【每日一题】子序列 题解

Solution

这公式看起来挺吓人，但转换一下就发现好像并没有那么难。

会发现后面式子中的是原来数组中的下标，与新构成的子序列并没有任何关联。

那么显然用高中导数题中经常使用的分离参数法解决：

两边取对数（任意底均可）：

即

令，那么就是找b数组的严格上升子序列的个数了。

那么就是个经典动态规划了，表示以第个位置为结尾的严格上升子序列的个数，那么有：

时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 100 + 10, MOD = 1e9 + 7;
int dp[N];
double a[N];
void add(int &x, int y) {
  x += y;
  if(x >= MOD) x -= MOD;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n; cin >> n;
  for(int i = 1; i <= n; i++) {
    int t; cin >> t;
    a[i] = log(t) / i;
  }
  for(int i = 1; i <= n; i++) {
    dp[i] = 1;
    for(int j = 1; j < i; j++) {
      if(a[j] < a[i]) {
        add(dp[i], dp[j]);
      }
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    add(ans, dp[i]);
  }
  cout << ans << '\n';
}

Addtion

上司看到上面这段代码后表示非常地不满意，这垃圾程序复杂度居然高达。

为了留住饭碗，灵机一动想到了复杂度的算法。

先预处理完上面所说的数组后，使用离线大法，将数组进行排序，如果比较小则先进行计算其值，如果和相同，则下标靠后的先进行计算。这样就不用顾虑大小顺序的问题了，直接求前缀和即可。再用一个树状数组动态地求一下前缀和即可。

时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 105, MOD = 1e9 + 7;
void add(int &x, int y) {
  x += y;
  if(x >= MOD) x -= MOD;
}
int base[N], id[N];
double a[N];
void upd(int at, int x) {
  for(int i = at; i < N; i += i & (-i)) {
    add(base[i], x);
  }
}
int query(int at) {
  int ret = 0;
  for(int i = at; i > 0; i -= i & (-i)) {
    add(ret, base[i]);
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n; cin >> n;
  for(int i = 1; i <= n; i++) {
    int t; cin >> t;
    a[i] = log(t) / i;
  }
  iota(id + 1, id + n + 1, 1);
  sort(id + 1, id + n + 1, [&](const int &x, const int &y) {
    if(a[x] == a[y]) return x > y;
    return a[x] < a[y];
  });
  for(int i = 1; i <= n; i++) {
    const int j = id[i];
    upd(j, 1);
    upd(j, query(j - 1));
  }
  cout << query(n) << '\n';
}