【每日一题】子序列(dp+math)

很水的一道题目。
唯一的难点可能就是，你要知道log这个函数。
使用它要包含math头文件，然后他返回的是浮点型的数据，我们如果直接去比较 其实是不好的，因为有可能会溢出，你long long 都没有用，你想想如果出现 ，这是个多大的数字啊。那我们就可以使用log这个函数了，比较上面的函数我们其实要分情况讨论一下，如果a[j]==1,那么一定不行，因为你a[i]^j不可能小于1了。那么反过来想想，如果a[j]!=1&&a[i]==1的时候，一定满足条件。那么剩下的就是a[j]!=1&&a[i]!=1的case了，我们再去使用log函数进行比较

return j*log[a[i]]<i*log(a[j]);

那么理清楚思路就好做了，我们可以仿造最长上升子序列的做法，dp[i]表示a[1]到a[i]以a[i]结尾的子序列的个数，那么很容易得出一个转移方程，当然这里还要初始化dp[0]=1,原因是不选也是一方案数，具体见代码

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