UVA10534 Wavio Sequence

题意：给你一串序列，让你序列中找出 类似这样的  1 2 3 4 5 4 3 2 1 的最大长度的子串，子串特性：1长度可以写成2*n+1，其中前n+1的序列是严格上升的，后n+1个是严格递减的；

一开始我的思路是这样的：第一遍先dp一遍，找出所有的递增序列，并且记录上升序列最后一个元素的位置，第二遍 从这些上升序列的最后一个元素的位置开始寻找，若能找到一个长度与上升相等的 下降序列就停止可以输出了，而且要从最长的开始找，这个想法 个人认为是没有什么问题的，但是写起来比较难处理，很难表达，后来又重新换了个思路：

先顺着dp一遍，再逆着dp一遍，都dp上升序列，第二遍dp的是它的逆序，而且对于符合性质的子串 他们的 dp1[i] == dp2[n - i + 1],这个稍微推一下就知道了，这样就比较好处理了，直接正反一次 nlong方法即可，但是原先的版子有问题，后来换了个版子过了，

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

//#define ll long long

#define  ll __int64

#define eps 1e-7

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)  
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) 

int dp1[100000 + 5];
int num[10000 + 5];
int dp2[100000 + 5];
int tmp[10000 + 5];

int n;

void clear() {
	memset(dp1,0,sizeof(dp1));
	memset(num,0,sizeof(num));
	memset(dp2,0,sizeof(dp2));
	memset(tmp,0,sizeof(tmp));
}

void LIS(int *dp,int *a) { // nlogn的LIS,n^2会超时的
	int Stack[10000 + 5];
	Stack[0] = -1;
	int top = 0;
	for(int i=1;i<=n;i++) {
		int left = 1;
		int right = top;
		int pos = -1;
		while(left <= right) {
			int mid = (left + right)/2;
			if(Stack[mid] < a[i])
				left = mid + 1;
			else 
				right = mid - 1;
		}
		Stack[left] = a[i];
		dp[i] = 1;

		if(a[i] > Stack[top]) {
			Stack[++top] = a[i];
			dp[i] = top;
		}
	}
}


int main() {
	while(scanf("%d",&n) == 1 ) {
		clear();
		for(int i=1;i<=n;i++) {
			scanf("%d",&num[i]);
			tmp[n - i + 1] = num[i];//tmp相当于num的倒序
		}
		LIS(dp1,num);
		LIS(dp2,tmp);
		int ans = -1,temp = 0;
		for(int i=1;i<=n;i++) {
			temp = min(dp1[i],dp2[n - i + 1]) * 2 - 1;//记得找小的那个
			ans = max(temp,ans);
		}
		printf("%d\n",ans);
	}
	return EXIT_SUCCESS;
}

UVA10534 Wavio Sequence

原文：http://blog.csdn.net/yitiaodacaidog/article/details/19170745