//＜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
using namespace std; int maxm(int a, int b) { if(a >= b )return a ; else return b; } const int maxn = ; 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; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214355.html原文链接：https://javaforall.net
