子序列

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

思路：

同理由

得：

所以当 并且 时

所以：

用一个dp数组计数，dp[i]为以a[i]结尾满足条件的个数

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 1000000007

int a[105];
ll dp[105];
double b[105];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=log10(a[i]);
        dp[i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=i-1;j>0;j--)
        {
            if(b[i]*j>i*b[j])
            {
                dp[i]=(dp[i]+dp[j])%inf;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+dp[i])%inf;
    }
    printf("%d\n",ans);
    return 0;
}