NC17065 子序列（简单dp）

题意

小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), 成立。

分析

，我们同时取对数，就有：
移一下项，可以得到：
于是子序列满足的条件相当于 单调增。
那这个问题就很简单了啊。。
设 表示以 结尾的子序列个数。
那么
最后 还要加上 ，因为一个数本身可以作为子序列。
那么 即可。

代码如下

#include <bits/stdc++.h>
#define N 105
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int mod = 1e9 + 7;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int f[N], a[N], ans;
int main(){
    int i, j, n, m;
    n = read();
    for(i = 1; i <= n; i++) a[i] = read(), f[i] = 1;
    for(i = 1; i <= n; i++){
        for(j = 1; j < i; j++){
            if(log(a[j]) / j < log(a[i]) / i) f[i] = (f[i] + f[j]) % mod;
        }
        ans = (ans + f[i]) % mod;
    }
    printf("%d", ans);
    return 0;
}