AtCoder Beginner Contest 468
取最大值AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a positive integer $N$ and a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.
给定一个正整数 $N$ 和 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$。AI (CI翻译)
There are variables $x,y,c$. Initially, $x=y=c=0$.
有三个变量 $x,y,c$。初始时，$x=y=c=0$。AI (CI翻译)
For $k=1,2,\ldots,N$ in this order, you perform one of the following operations:
按照 $k=1,2,\ldots,N$ 的顺序，对于每个 $k$，执行以下两种操作之一：AI (CI翻译)
- Operation
$1$: Increase$c$by$1$if$x < P_k$. Then, replace$x$with$\max(x,P_k)$. - Operation
$2$: Increase$c$by$1$if$y < P_k$. Then, replace$y$with$\max(y,P_k)$.
- 操作 1：如果
$x < P_k$，则将$c$增加$1$。然后，将$x$替换为$\max(x,P_k)$。 - 操作 2：如果
$y < P_k$，则将$c$增加$1$。然后，将$y$替换为$\max(y,P_k)$。
Find the maximum possible final value of $c$.
求 $c$ 最终可能达到的最大值。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1\le N\le 5\times 10^5$$P$is a permutation of$(1,2,\ldots,N)$.- All input values are integers.
$1\le N\le 5\times 10^5$$P$是$(1,2,\ldots,N)$的一个排列。- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入中给出，格式如下：AI (CI翻译)
N
P_1 P_2 \ldots P_NN
P_1 P_2 \ldots P_NOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
5
4 3 1 2 5
Output #1
4
By performing the operations as follows, you can achieve $c=4$:
- For $k=1$: Perform operation $1$. Then, $(x,y,c)=(4,0,1)$.
- For $k=2$: Perform operation $1$. Then, $(x,y,c)=(4,0,1)$.
- For $k=3$: Perform operation $2$. Then, $(x,y,c)=(4,1,2)$.
- For $k=4$: Perform operation $2$. Then, $(x,y,c)=(4,2,3)$.
- For $k=5$: Perform operation $2$. Then, $(x,y,c)=(4,5,4)$.
$c$ cannot be made greater than $4$ no matter how you perform the operations, so output $4$.
Input #2
6
6 5 4 3 2 1
Output #2
2
Input #3
9
3 6 5 2 7 8 9 1 4
Output #3
7
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。