题目

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

输入描述：
第一行一个整数n (1≤n≤100)表示序列长度。
接下来一行n个整数{a1,a2,a3,...,an}(1≤ai≤100)表示序列。

输出描述：
输出一行表示满足条件的子序列的数目。因为答案可能很大，请输出答案mod 1e9 + 7。

解析

这道题一看就发现是dp的题目，没有像大佬们用了树状数组啥的（我不会）
  • dp其实我都不咋会，但是还是不厌其烦的说：动态规划最基本的就是递推。

所以我们只要能得出递推公式，这道题就很简单了。
  1. 我们这道题根据题目意思就是，两个节点之间需要满足一定的关系：apipj < apjpi，才可计数。
  2. 从这里我们可以想到节点与节点之间的传递性（不好意思我没想到，感谢邓老师）。
  3. 我所说的传递性简单来说就是：假如有三个点：a，b，c。如果ab和bc之间同时存在这种关系，ac也存在这种关系。（我们下一点来证明一下）
  4. 首先根据题目条件：apipj < apjpi。我们在两边取对数可以得到。然后我们就发现移项后得到：。说明单调递增，当然有传递性。
    （什么？你问我为什么取对数？别问，问就是经验）（其实还有就是防止数据溢出）
  5. 传递性又能干啥呢？：我们先用一个dp数组保存一定区间内，并包含区间末节点的方法数（例如dp[pos]，dp区间为pos之前，并且表示的方法中一定包含pos位置上的节点）。
    而从传递性中我们可以发现，每一个满足条件的数据都可以继承与他相关的方法数（例如x与y有关系，y一定包含x的所有方法数：x所有的方法加一个y没有影响）。
  6. 最后对每个位置上的求和就是方法总数。详情看代码趴~~~

AC代码 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
//代码预处理区

const int MOD = 1e9 + 7;
const int MAX = 1e2 + 7;
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
//函数预定义区

int main() {
    int n; read(n);
    int a[MAX], dp[MAX];
    for (int i = 1; i <= n; i++)
        read(a[i]);
        //数组输入
    fill(dp + 1, dp + 1 + n, 1);
    for (int right = 1; right <= n; right++)
        for (int left = 1; left < right; left++)
            if (right * log(a[left]) < left * log(a[right]))
                dp[right] = (dp[right] + dp[left]) % MOD;
        //根据递推公式计算
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum = (sum + dp[i]) % MOD;
        //答案为方案总数：求和
    printf("%d", sum);
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区