子序列

题意:构成要求的序列,然后问能构成多少个
题解:两层暴力.......
我们先看式子化简:

咦,与最长递增子序列(LIS)相似,最长递增子序列可以参考这个:https://blog.csdn.net/ronaldo7_zyb/article/details/81052793
LIS返回表示最长递增子序列的长度
而本题要的是有多少个递增子序列.
相当于代码替换下就欧克了
==>
当然上述代码是不完整的换成数学语言就是:

可能有些不清楚,这样解释下:

对于1号位置为终点,满足递增子序列有(1)
对于2号位置为终点,满足递增子序列有(1)(3)(1,3)
对于3号位置为终点,满足递增子序列有(1)(3)(5)(1,3)(1,5)(3,5)(1,3,5)
对于4号位置为终点,满足递增子序列有(1)(2)(1,2)
.....
然后对与全局满足递增子序列,即上面的全部累加求和
时间复杂度:

#include<bits/stdc++.h>
using namespace std;

const int P = 1000000007;
int a[1001], n, f[1001];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++)
            if (log(a[j]) / j < log(a[i]) / i)
                f[i] += f[j],
                f[i] %= P;
        ++f[i]; f[i] %= P;
    }
    for (int i = 1; i <= n; i++)
        ans += f[i],
        ans %= P;
    printf("%d\n", ans);
}