2023NOIP A层联测9-天竺葵

题目

暂且把这个问题叫做带权最长上升子序列。

显然，类似于求 $LIS$，如果我们在 $a$ 序列的前 $i$ 个数中已经选了一个好的序列 $c$，那么 $c$ 的最后一个一定是最小的（因为后面更容易满足条件增加长度）。

于是用二分，$lo{w}_i$ 表示长度为 $i$ 的带权最长上升子序列的 $a_i\cdot b_i$ 的最小值。

每次用 $\text{lower\_bound}$ 在 $low$ 中查找大于等于 $a_i$ 的第一个位置，用 $a_i\cdot b_i$ 更新该位置，同时记录答案。

这样就做完了。

细节详见代码。

#include
using namespace std;
typedef long long ll;
int n,ans=1;
ll a[1000001],b[1000001],low[1000001];
ll read()
{
    ll sum=0;
    int c=getchar();
    while(c<48||c>57) c=getchar();
    while(c>=48&&c<=57) sum=sum*10+c-48,c=getchar();
    return sum;
}
int main()
{
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    memset(low,0x3f,sizeof(low));
    for(int i=1;i<=n;i++){
        int czn=lower_bound(low+1,low+1+ans,a[i])-low;
        ans=max(ans,czn);
        low[czn]=min(a[i]*b[czn],low[czn]);
    }
    cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28