NC17065 子序列_牛客博客

Question

一个由n个元素组成的序列 $\{a1,a2,a3,...,an\}$ ，她想知道其中有多少个子序列 $\{a_p1,a_p2,...,a_pm\}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)$ ，满足对于所有的 $i,j(1 ≤ i < j ≤ m), a_{pi}^{pj} < a_{pj}^{pi}$ 成立。

Solution

盲猜当满足 $a_{pi}^{pj} < a_{pj}^{pi}$ 时前后都是单调递增的。
严格证明图片说明 (来源于雨巨的题解！~~我估计我可能真的做的时候会盲猜试一发，或许这是一种直觉？~~)
然后DP求对应的贡献即可，设 $f[i]$ 表示必选第i个的情况下有多少种满足的取法, $f[i]=\sum_{j=1}^{i-1}f[j]$ 且满足 $a_{pi}^{pj} < a_{pj}^{pi}$ 。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 100 + 5;

int n,a[N],f[N];

bool check(int x,int y){
    if(y*log(a[x])<x*log(a[y])) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[0]=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(check(j,i)) f[i]+=f[j];
        }
        ans+=f[i];
    }
    cout<<ans;
    return 0;
}