首页 > 代码库 > codeforces 446A DZY Loves Sequences
codeforces 446A DZY Loves Sequences
codeforces 446A DZY Loves Sequences 题目链接:http://codeforces.com/problemset/problem/446/A
题目大意:给出一个定长为n的数列a,问修改其中一个数后,可能出现的最长严格上升子段的长度是多少。
题目分析:先不考虑“修改其中一个数”这个条件,这样问题就简单多了,从前到后遍历计数即可(定义一个数组inc[]长度同a,初始化所有点为1,遍历如果当前点a[i]>a[i-1]就置inc[i]=inc[i-1]+1)。那么加上修改一个数这个条件,问题变成什么样了呢?原数列里可能会有一些离散的严格上升子段,它们有的可以接续成一段(当两个严格上升子段中间只隔着一个数&&前一段的段末小于后一段的段头-1时,我们可以把隔在中间的那个数修改使其符合要求),也许不存在这样的两段,那么答案就是最长的一段的长度+1(如果数列本身就是严格上升的,答案就是n)。
总之就是找最长,其它情况好说,两段接续怎么搞呢?先用刚才提到的inc数组记下所有从前向后找的结果,可以在遍历时直接得到第i-1个点所在子段的最大长度,那么第i+1个点就需要反其道而行,再定义一个dec数组,从后向前遍历计数,两数组配合求得接续情况的最大值(可能说的不够清楚,详参代码)。
code:
#include<stdio.h> #include<string.h> int max(int a,int b,int c) { if(c>=a&&c>=b)return c; return a>b?a:b; } int main() { int i,j,n,a[100020],inc[100020],dec[100020],ans=0; scanf("%d",&n); if(n==1||n==2) { printf("%d\n",n); return 0; } for(i=0;i<n;i++) { scanf("%d",a+i); } inc[0]=dec[n-1]=1; for(i=1;i<n;i++) { inc[i]=a[i]>a[i-1]?inc[i-1]+1:1; dec[n-i-1]=a[n-i-1]<a[n-i]?dec[n-i]+1:1; } for(i=1;i<n-1;i++) { int temp=-1; if(a[i-1]<a[i+1]-1&&(inc[i]==1||dec[i]==1))temp=inc[i-1]+dec[i+1]+1; else if(a[i-1]<a[i])temp=inc[i-1]+2; else if(a[i]<a[i+1])temp=dec[i+1]+2; else temp=max(inc[i-1]+1,dec[i+1]+1,0); //if(temp>ans&&temp>inc[i])printf("temp==%d\n",temp); ans=max(temp,ans,inc[i]); } ans=max(ans,inc[n-2]+1,dec[1]+1); //由于上面的循环是从第二个跑到倒数第二个,所以最后需要这样收一下尾 printf("%d\n",ans); return 0; } /* 5676345 5676789 5678345 6 7 2 3 1 4 5 inc 1 1 2 1 2 3 dec 1 2 1 3 2 1 */
PS:题目只要求改一个数,如果变成改m个数该怎么办呢?我想应该在遍历时记下最优修改点,一遍遍历结束后真的去修改数组a、inc、dec的值,然后再去遍历,这样时间复杂度会骤增为原来的m倍,也许需要更优化的数组存储方法……
codeforces 446A DZY Loves Sequences
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。