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

• CSP模拟52联测14 C.天竺葵
  • 题目大意
  • 思路
  • code

题目大意

给定两个长度为 \(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;
}