NC17065 子序列题解

这题的关键在于不等式的化解，化出来之后就是一道简单的dp题了。
不等式中包含两个数字的位置，乍一看，选择的数字位置不同，比较结果也不相同。如果能证明位置(i,j),位置(j,k)都满足不等式的话，位置(i,k)也满足不等式，这题就简单了。
遇到有指数的不等式，很自然的想到两边取对数

$a_i^j<a_j^i \\=> j*ln(a_i)<i*ln(a_j) \\=>ln(a_i)/i < ln(a_j)/j$
于是我们发现实际上就是需要求出 $ln(a_i)/i$ 的值递增的子序列种数。
用 $dp[i]$ 表示以第i个位置为结尾可以得到的这样的子序列的种数，则

$dp[i]=\sum_{j=1}^{i-1}dp[j]*[ln(a_j)/j <ln(a_i)/i]$
答案 = 所有可能的子序列 = $\sum_{i=1}^ndp[i]$

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

NC17065 子序列 题解

NC17065 子序列题解