CF 446A DZY Loves Sequences
문제풀이 깨달음: 원래 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 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.