CSP模拟52联测14 C.天竺葵

CSP模拟52联测14 C.天竺葵

题目大意

给定两个长度为 $n$ 的序列 $a , b$

需要在 $a$ 序列中好到最长的序列 $c$ 满足 $c _{i + 1} > b_i \times c_i$

输出长度

$1\le n\le 10^6$

思路

感觉和 $n(\log n)$ 求最长上升子序列差不多

考虑 $dp$

设 $dp_i$ 为第 $c_i$ 的最小值

朴素的转移是 $O(n^2)$ 的

70分代码

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)

#define LL long long

using namespace std;
const int N = 1e6 + 5;
const LL inf = 1e12 + 5;
int n , ans , ans1 , lis[N] , len;
LL f[N] , a[N] , b[N] , min1;
int fans (int l , int r , LL x) {
    if (l == r) {
        return a[lis[l]] > x ? l : inf;
    }
    else {
        int mid = l + r >> 1;
        if (a[lis[mid]] >= x) return min (mid , fans (l , mid , x));
        else return fans (mid + 1 , r , x);
    }
}
int main () {
    freopen ("C.in" , "r" , stdin);
    freopen ("C.out" , "w" , stdout);
    int flg = 0 , x;
    scanf ("%d" , &n);
    fu (i , 1 , n) scanf ("%lld" , &a[i]);
    fu (i , 1 , n) {
        scanf ("%lld" , &b[i]);
        if (b[i] != 1) flg = 1;
    }
    if (!flg) {
        lis[len = 1] = 1;
        fu (i , 2 , n) {
            if (a[lis[len]] < a[i]) {
                lis[++len] = i;
                continue;
            }
            x = fans (1 , len , a[i]);
            lis[x] = i; 
        }
        printf ("%d" , len);
        return 0;
    }
    ans = 1 , f[1] = a[1];
    min1 = a[1];
    fu (i , 2 , n) f[i] = 1e12 + 5;
    fu (i , 2 , n) {
        ans1 = 0;
        fu (j , 1 , ans + 1) {
            if (a[i] > f[j - 1] * b[j - 1]) {
                f[j] = min (f[j] , a[i]);
                ans1 = max(ans1 , j);
            }
        }
        min1 = min (min1 , a[i]);
        ans = max (ans , ans1);
    }
    printf ("%d" , ans);
    return 0;
}

我们发现是转移的时候太慢了。

假设当前要处理的是 $a_i$

我们把现在的 $dp$ 分成两部分前 $k$ 个是小于 $a_i$ 的，后 $k$ 个是大于 $a_i$ 的

因为 $dp_{1\to k} \le a_i$ ，所以 $min_{j = 1 }^k (dp_j ,a_i)= dp_i $

因为 $dp_{k + 1 \to len} > a_i$ ，所以 $a_i < dp_j *b_j (j\in[k + 1 , len])$

所以现在要更新的就只有 $dp_k$

直接遍历一遍，二分查找 $k$ 就好了

时间复杂度 $O(n\log n)$

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 1e7 + 5;
const LL inf = 1e12 + 5;
int n , ans , ans1 , lis[N] , len;
__int128 f[N] , a[N] , b[N] , min1;
int fans (int l , int r , LL x) {
    if (l == r) {
        return a[lis[l]] > x ? l : inf;
    }
    else {
        int mid = l + r >> 1;
        if (a[lis[mid]] >= x) return min (mid , fans (l , mid , x));
        else return fans (mid + 1 , r , x);
    }
}
int main () {
    freopen ("C.in" , "r" , stdin);
    freopen ("C.out" , "w" , stdout);
    LL x;
    scanf ("%d" , &n);
    fu (i , 1 , n) scanf ("%lld" , &x) , a[i] = x;
    fu (i , 1 , n) scanf ("%lld" , &x) , b[i] = x;
    int k;
    ans = 1 , f[1] = a[1];
    min1 = a[1];
    fu (i , 2 , n) {
        k = lower_bound(f + 1 , f + ans + 1 , a[i]) - f - 1;
        if (k == ans) {
            if (a[i] > b[ans] * f[ans]) f[++ans] = a[i];
        }
        else {
            if (a[i] > b[k] * f[k]) f[k + 1] = a[i];
        }
    }
    printf ("%d" , ans);
    return 0;
}