// uva 10534 Wavio Sequence// // 可以将题目转化为经典的LIS。// 从左往右LIS记作d[i],从右往左LIS记作p[i];// 则最后其中的min(d[i],p[i])就是这个波动序列的一半// 在这最后的min(d[i],p[i]) * 2 + 1 的最大值就是我们所要求的答案//// 这题开始想的最后的答案是d[i]==p[i]的时候求最大。// 但是这样是不对的，例如n=4,// 1,3,1,0// 最长的应该是3，，但是我的答案是1，明显是错的//// 仔细想来，确实是这样，只要取min(d[i],p[i])的最小值作为一半就可以了//// 还是欠缺考虑，继续练#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);const int maxn = 10008;const int inf = 0x7f7f7f7f;int a[maxn];int b[maxn];int d[maxn];int p[maxn];int g[maxn];int n;void lis(int a[],int d[]){memset(g,inf,sizeof(g));int k;for (int i=1;i<=n;i++){k = lower_bound(g+1,g+n+1,a[i])-g;d[i] = k;g[k] = a[i]; }}void print(int a[]){for (int i=1;i<=n;i++){printf("%d ",a[i]);}puts("");}void init(){for (int i=1;i<=n;i++){scanf("%d",&a[i]);b[n-i+1] = a[i];}memset(d,inf,sizeof(d));memset(p,inf,sizeof(p));lis(a,d);lis(b,p);int ans = 1;for (int i=1;i<=n;i++){//if (d[i]==p[n-i+1]){//cout << i << "—-" << d[i] << endl;//ans = max(ans,d[i] * 2 – 1);//}ans = max(ans,min(d[i],p[n-i+1]) * 2 – 1);}printf("%d\n",ans);print(d);print(p);}int main() {//freopen("E:\\Code\\1.txt","r",stdin);while(scanf("%d",&n)!=EOF){init();}return 0;}
多看书，看好书。
