[noip2013] 꽃장인DP||욕심

설명 입력 Input Description

출력 설명 Output Description

샘플 Sample Input 입력

샘플 출력 Sample Output

데이터 범위 및 프롬프트 Data Size & Hint

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int size=100010;

int num[size];
int dp1[size][2],dp2[size][2];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        dp1[i][0]=dp1[i][1]=1;
        dp2[i][0]=dp2[i][1]=1;
        for(int j=1;j<i;j++)
        {
            if(num[j]<num[i])
            {
                dp2[i][0]=max(dp2[i][0],dp2[j][1]+1);
                dp1[i][1]=max(dp1[i][1],dp1[j][0]+1);
            }
            if(num[j]>num[i])
            {
                dp1[i][0]=max(dp1[i][0],dp1[j][1]+1);
                dp2[i][1]=max(dp2[i][1],dp2[j][0]+1);       
            }
        }
        ans=max(ans,max( max(dp1[i][0],dp2[i][0]) , max(dp1[i][1],dp2[i][1]) ) );
    }
    printf("%d",ans);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;


int main()
{
    int n,ans1=1,ans2=1;
    scanf("%d",&n);
    for(int i=1,last,x;i<=n;i++)
    {
        scanf("%d",&x);
        if(i==1) {last=x;continue;}
        if(last<x) {ans1=max(ans1,ans2+1);}
        if(last>x) {ans2=max(ans2,ans1+1);}
        last=x;
    }
    printf("%d",max(ans1,ans2));
    return 0;
}