2023NOIP A层联测9 T3 天竺葵
Ps:连接为accoderOJ。
看题大概是一个最长上升子序列的带权版本，于是想到 dp。
设 \(dp[i][j]\) 为到第 \(i\) 项，选出 \(j\) 个数的 \(c_j\) 最小值，不难想到转移：
\[dp[i][j]=\min(dp[i-1][j],a[i]\ (a[i]>dp[i-1][j]*b[j])\ )
\]
若任意 \(b_i>1\) ，那么答案长度不超过 \(50\) 个（每次 \(c_i\) 都要比至少 \(c_{i-1}*b_{i-1}\) 大，而 \(b_i-1\) 大于 \(1\) 所以可以很快接近 \(a_i\) 的上限）。
进一步，发现 \(dp[i]\) 具有随 \(j\) 上升的单调性，所以把 \(dp[i]\) 通过 \(a[i]\) 分为两部分，第一部分 \(dp[i][j]\) 均小于 \(a[i]\)，第二部分 \(dp[i][j]\) 均大于等于 \(a[i]\)。
那么对于小于 \(a[i]\) 的那一部分 \(dp[i][j]\) 根据转移方程肯定等于 \(dp[i-1][j]\)，对于大于等于的那一部分 \(dp[i][j]\) 除第一个位置外，其他的位置的 \(dp[i][j]*b[j]\) 一定有 \(a[i] \leq dp[i][j]*b[j]\)，所以可以更新的位置只有一个，那么每次更新一个位置即可。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int n,ans;
int a[maxn],f[maxn],b[maxn];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
memset(f,0x7f,sizeof(f));
for(int i=1;i<=n;i++)
{
int pos=lower_bound(f+1,f+n+1,a[i])-f;
if(a[i]>b[pos-1]*f[pos-1]) f[pos]=min(f[pos],a[i]);
}
for(int i=1;i<=n;i++) if(f[i]!=f[0]) ans=i;
printf("%lld",ans);
}