CF446A DZY Loves Sequences
loves sequences
2023-09-11 14:20:14 时间
CF446A DZY Loves Sequences
题目描述
给一个长度为n的序列a,定义ai,ai+1,ai+2....aj(1<=i<=j<=n)的长度为j-i+1,你可以最多更改一个数字,求最长的严格递增子段
输入格式
第一行包含n(1<=n<=105)表示序列长度。下一行包含a1到an(1<=ai<=109)
输出格式
输出最长的递增子段的长度
说明
你可以选择a2,a3,a4,a5,a6并且将a4更改为4
题解:
一开始的想法是按正常思路DP,设状态为dp[i] [0/1/2]表示前i位没修改,修改了但是不是i,修改了i的最长长度。但是这样的DP是错误的,因为虽然我们把修改的位设出来了,但是我们并不知道它最终被修改成了什么,也就是说,假如这个数被修改使得其符合了前面的那部分,但是你并不保证它改完之后也符合后面的部分。
所以这个状态是错的,根据它的错误理由,我们想到了正确的设状态方式:\(l[i],r[i]\)分别表示以i结尾、以i开头的最长严格递增子段的长度。
初值是\(l[1]=r[n]=1\),也就需要正着来一遍,反着来一遍。先不用考虑修改,修改是在统计答案的转移时做到的。在答案转移时,把两侧的序列合法地拼起来(有条件转移),就统计出了答案。
代码:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int a[maxn],l[maxn],r[maxn];
int n,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
l[1]=r[n]=1;
for(int i=2;i<=n;i++)
if(a[i-1]<a[i])
l[i]=l[i-1]+1;
else
l[i]=1;
for(int i=n-1;i;i--)
if(a[i]<a[i+1])
r[i]=r[i+1]+1;
else
r[i]=1;
for(int i=1;i<=n;i++)
{
ans=max(ans,max(l[i-1]+1,r[i+1]+1));
if(a[i-1]+1<a[i+1])
ans=max(ans,l[i-1]+1+r[i+1]);
}
printf("%d\n",ans);
return 0;
}
相关文章
- 【Codeforces 444A】DZY Loves Physics
- 【Codeforces 446A】DZY Loves Sequences
- 【Codeforces 1114C】Trailing Loves (or L'oeufs?)
- 【BestCoder Round #93 1001】MG loves gold
- 【hdu 5996】dingyeye loves stone
- 【BestCoder Round #93 1004】MG loves set
- 【BestCoder Round #93 1002】MG loves apple
- Codeforces Round #FF (Div. 2) D. DZY Loves Modification 贪心+优先队列
- HDOJ 4876 ZCC loves cards
- As long as Binbin loves Sangsang
- Codeforces Round #254 (Div. 2) A. DZY Loves Chessboard
- Codeforces Round #FF (Div. 1) B. DZY Loves Modification
- HDU-4879-ZCC loves march(map+set+并查集)
- hdu 4873 ZCC Loves Intersection(大数+概率)
- CF 444B(DZY Loves FFT-时间复杂度)
- 【2014 Multi-University Training Contest 2 1002】/【HDU 4873】 ZCC Loves Intersection
- 刷题记录:牛客NC22596Rinne Loves Data Structure
- 刷题记录:牛客NC22598Rinne Loves Edges
- 刷题记录:牛客NC22600Rinne Loves Dynamic Graph
- 刷题记录:牛客NC22594Rinne Loves Graph