NC17065 子序列 题解

这题的关键在于不等式的化解，化出来之后就是一道简单的dp题了。
不等式中包含两个数字的位置，乍一看，选择的数字位置不同，比较结果也不相同。如果能证明位置(i,j),位置(j,k)都满足不等式的话，位置(i,k)也满足不等式，这题就简单了。
遇到有指数的不等式，很自然的想到两边取对数

于是我们发现实际上就是需要求出的值递增的子序列种数。
用表示以第i个位置为结尾可以得到的这样的子序列的种数，则

答案 = 所有可能的子序列 =

#include<bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
const int mod = 1e9 + 7;
int a[105];
int n;
int dp[105];
bool check(int j, int i){
    return log(a[j])*i < log(a[i])*j;
}
int main()
{
    cin>>n; fors(i, 1 , n+1) cin>>a[i], dp[i] = 1;
    fors(i, 2, n+1) fors(j, 1, i) if(check(j, i)) dp[i] = (dp[i] + dp[j])%mod;
    int ans = 0; fors(i,1, n+1) ans = (ans + dp[i])%mod;
    cout<<ans<<endl;
}