【noip2013】花匠

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数ℎ1, ℎ2, … , ℎn。设当一部分花被移走后，剩下的花的高度依次为g1,g2,… , gm，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的1≤i≤，有g2i  >g2i-1，同时对于所有的1≤i≤，有g2i  >g2i+1；

条件 B：对于所有的1≤i≤，有g2i  < g2i-1，同时对于所有的1≤i≤，有g2i  

注意上面两个条件在 m = 1时同时满足，当m > 1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

输入

输入文件为 flower.in。

输入的第一行包含一个整数，表示开始时花的株数。

第二行包含个整数，依次为ℎ1, ℎ2, … , ℎn，表示每株花的高度。

输出

输出文件为 flower.out。

输出一行，包含一个整数，表示最多能留在原地的花的株数。

样例输入

5
5 3 2 1 2

样例输出

3

题解

设dp[ i ][ 0/1 ] 表示在 i -1 位置到 i 位置是下降(0)还是上升(1)。

如果 a[ i ] > a[ i-1 ]  dp[ i ][ 1 ] = dp[ i-1 ][ 0 ] +1 ，否则 dp[ i ][ 1 ] = dp[ i-1 ][ 1 ] 。

如果 a[ i ] < a[ i-1 ]  dp[ i ][ 0 ] = dp[ i-1 ][ 1 ] +1 ，否则 dp[ i ][ 0 ] = dp[ i-1 ][ 0 ] 。

答案取 max ( dp[ n ][ 0 ] ，dp[ n ][ 1 ] ) 。

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long longconst int maxn=1e5+50;int dp[maxn][2],n,a[maxn];templatevoid read(T& aa){char cc; ll ff;aa=0;cc=getchar();ff=1;while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();if(cc=='-') ff=-1,cc=getchar();while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();aa*=ff;
}int main(){read(n);for(int i=1;i<=n;i++) read(a[i]);dp[1][0]=dp[1][1]=1;for(int i=2;i<=n;i++){if(a[i]>a[i-1]) dp[i][1]=dp[i-1][0]+1;else dp[i][1]=dp[i-1][1];if(a[i]1]) dp[i][0]=dp[i-1][1]+1;else dp[i][0]=dp[i-1][0];}cout<0],dp[n][1]);return 0;
}

转载于:https://www.cnblogs.com/rlddd/p/9813581.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！