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 ;
}
From:http://tw.wingwit.com/Article/program/Web/201405/30988.html
