本文主要是介绍uva 10534 Wavio Sequence | dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
又是一道dp，又是在叶大神还有滔神的指导下才做出来。。。弱orz。
题意：
本质是最长不下降子序列。直接求解dp[i] = max(dp[i],dp[j]+1),j 1.....i;（TLE）
Wavio Sequence：要求个数为奇数，并且遵循严格的递增和递减。
思路：
实际上，对于这题，只要正着一次求最长不下降子序列，再逆着求一次，答案基本出来。为什么要这样子做呢？因为Wavio Sequence肯定是金字塔的形状，就是一边严格递增，一边严格递减。那么我顺序，逆序各求一次最长不下降序列，就可以得到了每个数值两边所对应的小于数值本身的个数（重复的只算一个）。
*由于n的范围到了10^4，直接求解复杂度为O(N^2)，TLE。所以运用了线段树(可以用树状数组，速度会更快代码更简单，只可惜本人之前学过现在却不知道怎么写了了orz）来求解。
*而且怕数据会过大，进行了一次离散化,貌似滔神敲了一发，并没有离散化也过了。
res = max(res,min（dp[i],dp2[i])*2-1)就是结果了。
AC代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define lson x,mid,root<<1
#define rson mid+1,y,root<<1|1
const int NUM = 10005;
int dp[NUM],dp2[NUM];
int st[NUM<<2];
struct Str
{int site;int num;
} a[NUM];
bool cmp(Str a,Str b)
{return a.num < b.num;
}
bool cmp2(Str a,Str b)
{return a.site < b.site;
}
int LiShanHua(int n)
{sort(a,a+n,cmp);int tmp = 1;a[n].num = a[n-1].num;int res;for(int i = 1; i <= n; i++){if(a[i].num != a[i-1].num){a[i-1].num = tmp++;}else{res = tmp;a[i-1].num = tmp;}}sort(a,a+n,cmp2);return res;
}
int Query(int x,int y,int root,int t,int p)
{if(p == 0){return 0;}if(t <= x && y <= p){return st[root];}int mid = (x+y)/2;int Max;if(t <= mid){Max = Query(lson,t,p);}if(p > mid){Max = max(Max , Query(rson,t,p));}return Max;
}void Update(int x,int y,int root,int site,int times)
{if(x == y){st[root] = times;return;}int mid = (x + y)/2;if(site <= mid)Update(lson,site,times);elseUpdate(rson,site,times);st[root] = max(st[root<<1],st[root<<1|1]);
}int main()
{int n;while(cin>>n){for(int i = 0; i < n; i++){scanf("%d",&a[i].num);a[i].site = i;}int res = LiShanHua(n);memset(st,0,sizeof(st));for(int i = 1;i <= n;i++){int tmp = Query(1,res,1,1,a[i-1].num-1);dp[i] = max(1,tmp+1);Update(1,res,1,a[i-1].num,dp[i]);}memset(st,0,sizeof(st));for(int i = n;i >= 1;i--){int tmp = Query(1,res,1,1,a[i-1].num-1);dp2[i] = max(1,tmp+1);Update(1,res,1,a[i-1].num,dp2[i]);}int Max = -1;for(int i = 1;i <= n;i++){Max = max(Max,min(dp[i],dp2[i])*2 - 1);}printf("%d\n",Max);}return 0;
}
这篇关于uva 10534 Wavio Sequence | dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
