4.24 子序列

这是一道类似导弹拦截的dp题
首先式子可化为 log(a[j])/j<log(a[i])/i
然后用dp[i] 来表示以i位为结尾的子序列的个数

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