子序列（dp，LIS变形）

题目：

小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列{ap1,ap2,...,apm}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), $a_{pi}^{pj} < a_{pj}^{pi}$ 成立。
输出答案mod 1,000,000,007。
输入描述:

做法：

看似无从入手。但可以发现a[i]和下标i是捆绑的。 $a_{pi}^{pj} < a_{pj}^{pi}$ 这个东西移项变形一下： $\frac{\log{a_{pi}}}{p_i}< \frac{log{a_{pj}}}{p_j}$ 。那么我们求出每个 $\frac{\log{a_{i}}}{i}$ 形成一个 $b[i]$ 数组。问题就转化成在 $b[i]$ 上的LIS（最长上升子序列）dp问题。 $O(n^2)$ 解决问题。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 110;
const int mod = 1e9 + 7;
int a[N], dp[N];
double b[N];
int main(void){
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        b[i] = 1.0/i*log(a[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        dp[i] = 1;
        for (int j = 1; j < i; ++j){
            if (b[i] > b[j]) (dp[i] += dp[j]) %= mod;
        }
        (ans += dp[i]) %= mod;
    }
    cout << ans << endl;
    return 0;
}