Codeforces 447 C DZY Loves Sequences【DP】

题意：给出一列数，在这个序列里面找到一个连续的严格上升的子串，现在可以任意修改序列里面的一个数，问得到的子串最长是多少

看的题解，自己没有想出来

假设修改的是a[i],那么有三种情况，

1.a[i]>a[i-1],那么求出向左能够延伸的最长的长度

2.a[i]<a[i-1],那么求出向右能够延伸的最长的长度

3.如果修改的这个数刚好夹在两个数的中间，这种情况比上面两种都优，即为a[i-1]<a[i+1]-1，求出左右能够延伸的最长的长度

然后因为a[i]本身还没有算进去，所以求出最大值后，再加个1 参看的这一篇http://blog.csdn.net/hongrock/article/details/37754307

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int a[maxn],l[maxn],r[maxn];

 int main(){

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     for(int i=;i<=n;i++) {

         l[i]=;r[i]=;

     }

     for(int i=n-;i>=;i--) if(a[i]<a[i+]) r[i]+=r[i+];

     int ans=;

     for(int i=;i<=n;i++) if(a[i]>a[i-]) l[i]+=l[i-];

     l[]=-;r[n+]=-;

     a[]=INF;a[n+]=-;

     for(int i=;i<=n;i++){

         if(a[i-]<a[i+]-) ans=max(ans,l[i-]+r[i+]+);

         else ans=max(ans,max(l[i-],r[i+])+);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

Codeforces 447 C DZY Loves Sequences【DP】

最新文章

热门文章