CF 446A DZY Loves Sequences

3222 단어
제목 링크 ~~>
문제풀이 깨달음: 원래 A문제는 매우 간단할 줄 알았는데 물이 지나간 지 한참이 지나도 마지막에 두 번 끓지 않아서 드디어 AC가 되었다.
문제 해결 방법:
본인: 먼저 dp0[i]로 i를 종점으로 연속된 개수를 기록해 보세요.dp1[i]로 i를 끝으로 바뀐 연속 개수를 다시 한 번 기록합니다.하나를 바꾸면 몇 가지 상황으로 나눌 수 있다. (1) g[i-1]은 g[i-2]와 g[i]의 중간수->dp[i] = dp[i-2] + 2로 바꿀 수 있다.(2) g[i-1]가 g[i]보다 작으면 dp1[i] = max(dp1[i], dp[i-1] + 1, dp1 [i-1] + 1) 업데이트;(3) 그렇지 않으면 g[i-1], dp1[i]=2만 바꿉니다.
업데이트 ans는 주의해야 한다! 
좋은 사고방식: i를 종점으로 하는 최대 연속 개수를 L[i]로 기록하고 R[i]는 i를 기점으로 하는 최대 연속 개수를 기록한다.(1) g[i] - g[i-2]>= 2이면 ans = max {L[i-2] + R [i] +1, ans}.(2) 그렇지 않으면 ans = max {ans, L[i] +1, R [i] +1}
코드(우수 코드):
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const double esp = 0.0000001 ;
const int MX = 100000 + 10 ;
int ans,n ;
int g[MX],L[MX],R[MX] ;
int main()
{
    while(~scanf("%d",&n))
    {
        memset(L,0,sizeof(L)) ;
        memset(R,0,sizeof(R)) ;
        L[0]=1 ;
        n > 1 ? ans =2 : ans =1 ;
        for(int i=0 ;i<n ;i++)
        {
            scanf("%d",&g[i]) ;
            i&&g[i-1]<g[i] ? L[i]=L[i-1]+1 : L[i] = 1 ;
        }
        R[n-1]=1 ;
        for(int i=n-1 ;i>=0 ;i--)
           g[i]<g[i+1] ? R[i] = R[i+1]+1 : R[i] = 1 ;
        ans = max(R[1]+1,ans) ;
        for(int i=2 ; i<n ;i++)
          g[i]-g[i-2]>=2 ? ans = max(ans,L[i-2]+R[i]+1) : ans = max(ans,max(L[i-1]+1,R[i]+1)) ;
        cout<<ans<<endl ;
    }
    return 0 ;
}

코드(본인):
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const double esp = 0.0000001 ;
const int MX = 100000 + 10 ;
int ans,n ;
int dp1[MX],g[MX],dp[MX] ;
void init()
{
    memset(dp,0,sizeof(dp)) ;
    dp[0]=1 ;
    for(int i=1 ;i<n ;i++)
    {
        if(g[i]>g[i-1])
                dp[i]=dp[i-1]+1 ;
        else    dp[i]=1 ;
        ans = max(dp[i],ans) ;
    }
}
void solve()
{
    memset(dp1,0,sizeof(dp1)) ;
    dp1[0]=1 ;
    ans=1 ;
    if(n>=2)
       dp1[1]=2,ans =2 ;
    for(int i=2 ;i<n ;i++)
    {
        if(g[i]-g[i-2]>=2&&(g[i-1]==g[i-2]||g[i-1]==g[i]||g[i-1]>g[i]||g[i-2]>g[i-1]))
                        dp1[i]=dp[i-2]+2 ;
        else if(g[i-1]<g[i])
        {
            dp1[i] = max(dp1[i],dp[i-1]+1) ;
            dp1[i] = max(dp1[i],dp1[i-1]+1) ;
        }
        else dp1[i]=2 ;
        ans = max(dp1[i],ans) ;
        ans = max(dp[i-1]+1,ans) ;
    }
    cout<<ans<<endl ;
}
int main()
{
    while(~scanf("%d",&n))
    {
        ans = 0 ;
        for(int i=0 ;i<n ;i++)
            scanf("%d",&g[i]) ;
        init() ;
        solve() ;
    }
    return 0 ;
}

좋은 웹페이지 즐겨찾기