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);
}
标签:int,pos,T3,maxn,天竺葵,2023NOIP,dp,联测
From: https://www.cnblogs.com/binbinbjl/p/17757811.html