题意:小美有一个由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;
}