题解：P1970 [NOIP2013 提高组] 花匠

Co_Ce · 2025-01-12 10:06:42 · 题解

solution

传送门

分析

由条件可得：求一个最长序列，使该序列任意三个元素，中间为最大或最小。

思路

用 dp[i][0] 表示前 i 个元素是以 i 为中心的三个相邻的元素中的最大的。
用 dp[i][1] 表示前 i 个元素是以 i 为中心的三个相邻的元素中的最小的。
当 h[i]<h[i-1] 时，选 i，则 dp[i][1]=dp[i-1][0]+1，不选，则 dp[i][1]=dp[i-1][1]。
最后，输出 max(dp[n][1],dp[n][0])。

std：

#include<bits/stdc++.h>
using namespace std;
int n;
int dp[100010][5];
int h[100010]; 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    dp[1][0]=1;
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        h[i]>h[i-1]?dp[i][0]=dp[i-1][1]+1:dp[i][0]=dp[i-1][0];
        h[i]<h[i-1]?dp[i][1]=dp[i-1][0]+1:dp[i][1]=dp[i-1][1];
    }
    cout<<max(dp[n][1],dp[n][0]);
    return 0;
}