小菜菜说下这道题，因为不到15分钟搞定的，而且一次A了。
题意就是求最长的符合那个条件的序列，当然，不一定连续。

首先，如果没有任何符合条件的情况出现，那么最长的就是每个元素本身，长度为1。

思路：先说个概念，大元素：大于前面的，大于后面的。
从2出发，1是大元素。如果大元素遇见比它本身大的，则最大解不变，遇见的这个元素仍为大元素，如果遇见比它小的元素，则最大解+1，遇见的这个元素成小元素，下一个就考虑遇见的这个元素；
同样，如果是小元素遇见比它小的，则最优解长度不变，遇见的这个元素仍为小元素，如果是遇见比它大的，则最优解+1，遇见的这个元素为大元素，下一个就考虑遇见的这个元素；

我弄了这么个， int dp[30005][2];  dp[i][0]==1代表当前的第i个元素是作为大元素在序列中的（<[i]>），dp[i][0]==0代表当前的第i个元素是作为小元素在序列中的(> a[i] <)；dp[i][1]就是考虑前i个元素的的最大解。

代码太菜了，就不附了~~小菜。
有幸被牛人看见的话请不吝指教哈~
//752K 172MS~~

• Re:小菜菜说下这道题 (522) 1016037677 2012-05-26 22:30:03