NC17065-子序列-(数学+dp)

https://ac.nowcoder.com/acm/problem/17065

题意：有n个数的数组a，求数组的子序列个数，满足子序列 { a_p1,a_p2,...a_pm },p1<p2...<pm,使得子序列中的任意两个数满足a_i^j< a_jⁱ (i<j)。结果对1e9+7求模。

思路：看起来吓死人，对不等式一步步化简。

a_i^j< a_jⁱ

→ loga_i^j< log a_jⁱ

→ j*log a_i < i*log a_j

→ (log a_i)/i < (log a_j)/j

对于每一个数a_i可以处理出一个(log ai)/i的数，姑且叫做bi，这就变成了b数组的递增子序列问题，dp[i]表示以b_i结尾的子序列的个数，从样例数据可以知道每一个数本身就是一个子序列，dp[i]要初始化为1。对每一个b_i，寻找前面比它小的递增子序列个数与自己再构成递增子序列。时间复杂度O(n²)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

const ll p=1e9+7;
int n;
double b[105];
double c[105];///树状数组
ll dp[105];///以i结尾的符合要求的子序列有多少个

int main()///NC17065子序列 数论+dp
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        double x;
        scanf("%lf",&x);
        b[i]=log(x)/(double)i;
        dp[i]=1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(b[j]<b[i])
                dp[i]=(dp[i]+dp[j])%p;
        }
        ans=(ans+dp[i])%p;
    }
    printf("%lld
",ans);
    return 0;
}

NC17065-子序列-(数学+dp)

相关推荐