[NOIP 2013] 花匠

[题目链接]

         https://loj.ac/problem/2612

[算法]

        递推即可 ， 时间复杂度O(N)

[代码]

        

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2000010

int n,ans;
int a[MAXN];
int f[MAXN][2];

template <typename T> inline void read(T &x)
{
    int f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}

int main() 
{

        read(n);
        for (int i = 1; i <= n; i++) read(a[i]);
        f[1][0] = f[1][1] = 1;
        for (int i = 2; i <= n; i++)
        {
                if (a[i] > a[i - 1]) f[i][0] = f[i - 1][1] + 1;
                else f[i][0] = f[i - 1][0];
                if (a[i] < a[i - 1]) f[i][1] = f[i - 1][0] + 1;
                else f[i][1] = f[i - 1][1];
        }
        printf("%d
",max(f[n][0],f[n][1]));
        
         return 0;
    
}