【每日一题】4月24日子序列

讲到子序列，而且有大小关系，应该可以第一时间想到和动态规划有关系，带着这个思路，我们再看下题目。对于每个位置（i，j），都要存在 两边同时取对数，再相除得到 题目就变成了求以 为判断条件的递增子序列问题，问题规模比较小，可以直接二重循环遍历，也可以发现只和单个变量有关系，可以通过离散+树状数组取优化到时间复杂度O(N * log(N))

PlanA
PlanB

// A
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 105;
const int MOD = 1e9 + 7;
ll dp[N], ans;
int a[N], n;

int main() {
    n = read();
    for (int i = 1; i <= n; ++i)    a[i] = read(), dp[i] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j)
            if (i * log(a[j]) < j * log(a[i]))
                (dp[i] += dp[j]) %= MOD;
        (ans += dp[i]) %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}



/*

B
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
#define lowbit(x) (x&(-x))
const int N = 105;
const int MOD = 1e9 + 7;
ll p[N], s[N];
double a[N], b[N];
int c[N]; //离散化数组

void add(int x, int y) {
    while (x <= 100) {
        (s[x] += y) %= MOD;
        x += lowbit(x);
    }
}

ll query(int x) {
    ll ans = 0;
    while (x) {
        (ans += s[x]) %= MOD;
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        c[i] = read();
        a[i] = b[i] = log(c[i]) / i;
    }
    sort(b + 1, b + 1 + n);
    int cnt = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++i)
        c[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        p[i] = 1 + query(c[i] - 1);
        ans += p[i]; ans %= MOD;
        add(c[i], p[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

*/