首页 > 其他分享 >2023NOIP A层联测9 T3 天竺葵

2023NOIP A层联测9 T3 天竺葵

时间:2023-10-11 17:57:42浏览次数:36  
标签:int pos T3 maxn 天竺葵 2023NOIP dp 联测

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

相关文章

  • 正如ioi2023noip二十连游寄
    day1抽象场。T1是诈骗题,剩下三题都是撒币概率期望。赛事没有人过t3t4。毫无意义。T2想不到可以把相似的状态归在一起。从\(O(2^{3n})\)到\(O({\begin{pmatrix}n+m\\n\end{pmatrix}}^3)\),很难想到。不过foi的时候甚至听说过拆分数复杂度的题。day2信心场。但是我没有信......
  • 牛客提高模拟赛第四场 T3
    给你一个数\(n\),让你从\(n\)中取出若干数合并成\(x\),剩下数合并成\(y\),求对于所有取法\(x+y\)的和例如\(12345\)可以拿出\(24\),剩下\(135\),此时会对答案产生\(24+135\)的贡献。而\(42,153\)或\(23,15\)是不合法的\(n\leq10^{10^5}\)显然\(\sumx......
  • qbxt 突破营 Day7 T3
    小葱想要吃糖,小葱将拿出来的N颗糖排成一排,第\(i\)颗糖的美味值为\(a_i\)。小葱很喜欢吃糖,所以小葱会从\(N\)颗糖选择不超过\(K\)段不相交的区间的糖果吃掉。但是小葱同学不希望别人吃到和他美味度差不多的糖,所以对于一颗没被吃掉的糖,小葱希望这颗糖美味度比他吃的糖的美味度最大......
  • 紫书Unit3.字符数组
    charc语言中字符型关键字用char表示,实际储存的是字符的ascll码。字符串是以‘\0’结尾。同时,字符常量可以用单引号表示,'a',在语法上可以将字符当作int使用,`'a'+1会输出98; scanf输入charscanf("%s",s),遇到空字符会停下来。 //3.5TEX中的引号,将特定符号转化//输入"To......
  • 2023NOIP A层联测5
    A.T1(cook)复合题,考场上只做出来了分块的部分,没有想到那个组合数求和可以用莫队分块部分具体不说了,对散块部分加权时,可以采用归并优化时间复杂度(因为我北卡长哩,卡到了晚饭之后,卡了一下午,好欸!)现在考虑问题\(\sum_{i=0}^{k}\dbinom{x}{i}\)令$(S(n,m)=\sum_{i=0}^{m}C......
  • 2023NOIP A层联测6
    A.万花筒考虑发现每次相当于把x和x+d连边,不难发现最后一定是一些环证明可以看白简B.冒泡排序趟数期望写一下我曾经比较疑惑的点为什么inv和p一定一一对应,因为我们发现只要给出我们一个inv我们就可以倒推出唯一确定的p,所以它们是一一对应的关系这道......
  • ElasticSearch8.10.2接入SpringBoot3.+
    pom.xml文件引入依赖 <!--https://mvnrepository.com/artifact/org.elasticsearch.client/elasticsearch-rest-client--> <dependency> <groupId>co.elastic.clients</groupId> <artifactId>elasticsearch-java</artifactId> &l......
  • Springboot3
    Java17以上1.依赖<parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>3.0.0</version><relativePath/></parent>2.新特性2.1JakartaEE......
  • 联想T30瘦客户机安装DoraOS体验
    硬件配置:J4125、8GRAM、128GROM联想T30台式电脑,它是一台迷你计算机,尺寸小巧玲珑,重量适中,方便携带。它的性能十分强大,能够运行各种应用程序,包括网页浏览器、视频播放器等。它还支持多种操作系统,如Windows系统和Linux系统,用户可以根据自己的需求选择不同的操作系统。此外,这台计......
  • 如何在Nuxt3.0中使用MongoDB数据库
    一、介绍Nuxt.js是一个基于Vue.js的开源框架,用于构建服务端渲染(Server-SideRendering,SSR)或静态生成(StaticSiteGeneration,SSG)的单页应用(Single-PageApplications,SPA),可以用来作为全栈项目开发框架使用。本篇主要分享下我在使用Nuxt3.0项目做全栈项目开发时......