//<NOIP2013> 花匠
/*
最优子结构性质,可以用动规。注意到存在30%的变态数据(1 ≤ n ≤ 100,000,
0 ≤ h_i ≤1,000,000),因此应当找到线性的算法
。A、B两种情况不仅不会增加复杂性,反而消除了对n奇偶性的讨论。
两种情况可以简化为一种锯齿状的数列,只需讨论i前保留的花高度与花i的高度
h[i]的关系即可。
第i朵花的高度为h[i](1 <= i <= n),前i朵花“尾部为升序”的最长序列长度
为S1[i],“尾部为降序”的最长序列长度为S2[i]。
则有状态转移方程:
1. (h[i] > h[i-1]):S1[i] = max(S1[i-1], S2[i-1] + 1);S2[i] = S2[i-1];
2. (h[i] == h[i-1]):S1[i] = S1[i-1];S2[i] = S2[i-1];
3. (h[i] < h[i-1]):S1[i] = S1[i-1];S2[i] = max(S2[i-1], S1[i-1] + 1);
由此可以写出复杂度为O(n)的动态规划代码
*/
#include <cstdio>
using namespace std;
int maxm(int a, int b)
{
if(a >= b )return a ;
else return b;
}
const int maxn = 1000005;
int h[maxn] = {0}; //
int n;
int S1[maxn], S2[maxn] ;
//(s1[]尾部为升序,s2[]尾部为降序)
int main(void)
{
freopen ("FlowerNOIP2013.in","r",stdin);
freopen ("FlowerNOIP2013.out" ,"w",stdout);
scanf("%d", &n);
int i;
for(i = 1; i <= n; i++)
scanf("%d", &h[i]);
S1[1] = S2[1] = 1; //初始状态 for(int i = 2;i <= n; i++)
{
if(h[i] > h[i-1]) // case1
{
S1[i] = maxm(S1[i-1], S2[i-1]+1 );
S2[i] = S2[i-1];
}
else if (h[i] == h[i-1])// case2
{
S1[i] = S1[i-1];
S2[i] = S2[i-1];
}
else //case 3
{
S1[i] = S1[i-1];
S2[i] = maxm(S1[i-1]+1, S2[i-1] );
}
} printf("%d", maxm(S1[n], S2[n]) );
return 0;
}
04-13 18:23