【每日一题】子序列 题解

Solution

简单分析一下题意, 有一个式子, 式子看起来很复杂, 但是简单的讲就是
找的子序列
化简一下得到
再化简一下得到
那么我们先对数组都处理一下
然后问题就转化成求 上升子序列的个数
令 是以 结尾的子序列个数
那么有
于是

Code

/*
  autor: Kurisu
  2020年4月24日09:09:25
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 100 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;

int dp[105];
double a[N];
int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) dp[i] = 1;
  for(int i = 1; i <= n; i++) cin >> a[i], a[i] = log(a[i]) / i; // 处理一下
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j < i; j++) {
      if(a[j] < a[i]) {
        dp[i] += dp[j];
        dp[i] %= mod;
      }
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    ans = (ans + dp[i]) % mod;
  }
  cout << ans << "\n";
  return 0;
}