NC17065 子序列（简单dp）

题意

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

分析

$a_{pi}^{\small{pj}} < a_{pj}^{\small pi}$ ，我们同时取对数，就有： $p_jln(a_{p_i})<p_iln(a_{p_j})$
移一下项，可以得到： $\frac{ln(a_{p_i})}{p_i}<\frac{ln(a_{p_j})}{p_j}$
于是子序列满足的条件相当于 $\frac{ln(a_i)}{i}$ 单调增。
那这个问题就很简单了啊。。
设 $f_i$ 表示以 $i$ 结尾的子序列个数。
那么 $f_i=\sum{f_j}(\frac{ln(a_i)}{i}>\frac{ln(a_j)}{j})$
最后 $f_i$ 还要加上 $1$ ，因为一个数本身可以作为子序列。
那么 $ans=\sum\limits_{i=1}^{n}{f_i}$ 即可。

代码如下

#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;
}