|
Wavio is a sequence of integers It has some interesting properties · Wavio is of odd length ie L = *n + · The first (n+) integers of Wavio sequence makes a strictly increasing sequence · The last (n+) integers of Wavio sequence makes a strictly decreasing sequence · No two adjacent integers are same in a Wavio sequence For example is an Wavio sequence of length But is not a valid wavio sequence In this problem you will be given a sequence of integers You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence Consider the given sequence as : Here the longest Wavio sequence is : So the output will be Input The input file contains less than test cases The description of each test case is given below: Input is terminated by end of file Each set starts with a postive integer N(<=N<=) In next few lines there will be N integers Output For each set of input print the length of longest wavio sequence in a line
Sample Input Output for Sample Input Problemsetter: Md Kamruzzaman Member of Elite Problemsetters&#; Panel 题意求出最长的波形序列波形序列为前半部分上升后半部分下降长度相同 思路一开始以为是水水的LIS问题可是n有W用基本的dp复杂度为O(n^)果断超时了然后去了解了下一种算法i表示前i个数字组成的序列原来的做法是i遍历一遍为O(n)然后在i里面遍历一遍查找满足条件的最长序列为O(n)总复杂度为O(N^)现在查找满足条件换个方式先把序列保存下来如果最后一个数字大直接加在序列位置否则用二分查找法找到适当位置插入这样复杂度为O(logn)总复杂度为O(nlogn)不过这总方法保存只能求长度保存下得序列并不能满足题目 代码 #include <stdioh>#include <stringh>const int MAXN = ;int n num[MAXN] i j dp[MAXN] a[MAXN] b[MAXN] mi; int two_set(int i int j int key) { while (i < j) { int mid = (i + j) / ; if (dp[mid] == key) return mid; if (dp[mid] > key) j = mid; else i = mid + ; } return j;} int max(int a int b) { return a > b ? a : b;} int min(int a int b) { return a < b ? a : b;} int main() { while (~scanf(%d &n)) { j = ; for (i = ; i <= n; i ++) scanf(%d &num[i]); dp[j] = num[]; a[] = ; for (i = ; i <= n; i ++) { if (num[i] > dp[j]) { dp[++ j] = num[i]; a[i] = j; } else { mi = two_set( j num[i]); dp[mi] = num[i]; a[i] = mi; } } j = ; dp[j] = num[n]; b[n] = ; for (i = n ; i >= ; i ) { if (num[i] > dp[j]) { dp[++j] = num[i]; b[i] = j; } else { mi = two_set( j num [i]); dp[mi] = num[i]; b[i] = mi; } } int ans = ; for (i = ;i <= n; i ++) { ans = max(ans * min(a[i] b[i])); } printf(%dn ans ); } return ;} |
