|
Language:
Antimonotonicity
Description Mary数列是指在一个长度为n的序列（元素大小不超过n）中找到如下的子序列： Mary0 > Mary1 < Mary2 > Mary3 < ... 请求出它的最长序列大小。 Input 第一行为数据数 T ≤ 50 接下来T行，每行第一个数n(≤ 30000)表示原序列大小,接下来n个数为给定序列 Output
对每组数据输出一行为Mary数列最长长度。
Sample Input 4 5 1 2 3 4 5 5 5 4 3 2 1 5 5 1 4 2 3 5 2 4 1 3 5 Sample Output 1 2 5 3 Source
Waterloo Local Contest, 2007.7.14
|
这题和LIS有异曲同工之妙，都是在给定区间找最大值
显然可以建立两棵线段树（并互相传递值)，表示（...?<a[i]) 中使得“..”长度最长的大小，
由于用Unique（指针头，指针尾+1)离散了序列，用-INF和INF表示边界（特别注意离散Hash-map<int,int> Hpos一定要开在Struct外，否则反复建会超时（平衡树用来干这个……）
于是t.t[i][j] 表示第ith线段树的端点值。
i=0表示(1,3,5... 即除1外前面跟了<号的)的数
i=1表示(2,4,6... 即前面跟>的）数
于是本题转化为维护（..?<）的最长长度。
同理建立(..?>),注意特判序列开头那个数（第二个序列的长度必须超过1，表示其并非开头）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
#define MAXN (30000+10)
#define INF (2139062143)
#define NDEBUG
map<int,int> hpos;
struct SegMentTree //t[0]->'?<' t[1]->'?>'
{
int n,M,t[2][MAXN*5],a[MAXN],a_sort[MAXN],size;
SegMentTree(){}
SegMentTree(int _n):n(_n)
{
M=1;while (M-2<n) M<<=1;
memset(t,0,sizeof(t));
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
memcpy(a_sort,a,sizeof(a));
sort(a_sort+1,a_sort+n+1);
#ifndef NDEBUG
for (int i=1;i<=n;i++) cout<<a_sort[i]<<' ';
cout<<endl;
#endif
size=unique(a_sort+1,a_sort+n+1)-(a_sort+1);
#ifndef NDEBUG
for (int i=1;i<=size;i++) cout<<a_sort[i]<<' ';
cout<<endl;
cout<<size;
#endif
for (int i=1;i<=size;i++) hpos[a_sort[i]]=i;
hpos[-INF]=0;hpos[INF]=size+1;
}
void update(int x,int type)
{
for (x>>=1;x;x>>=1) t[type][x]=max(t[type][x<<1],t[type][(x<<1)^1]);
}
void insert(int x,int c,int type)
{
x=hpos[x]+M;
if (t[type][x]<c)
{
t[type][x]=c;
update(x,type);
}
}
int find(int l,int r,int type)
{
l=hpos[l];r=hpos[r];
// if (type) l++; else r--;
#ifndef NDEBUG
cout<<l<<' '<<r<<';'<<endl;
#endif
l+=M;r+=M;
int ans=0;
if (l>=r-1) return 0;
for (;l^r^1;l>>=1,r>>=1)
{
if (~l&1) ans=max(ans,t[type][l+1]);
if (r&1) ans=max(ans,t[type][r-1]);
}
return ans;
}
}t;
int tt,n,ans;
int main()
{
#ifndef NDEBUG
freopen("poj3298.in","r",stdin);
#endif
scanf("%d",&tt);
while (tt--)
{
ans=0;
scanf("%d",&n);
t=SegMentTree(n);
for (int i=1;i<=n;i++)
{
int value=t.a[i];
int value1=t.find(-INF,value,0)+1;
int value2=t.find(value,INF,1)+1;
t.insert(value,value1,1);
ans=max(ans,value1);
#ifndef NDEBUG
cout<<"Add?> "<<value<<" f[i]="<<value1<<endl;
#endif
if (value2==1) continue;
t.insert(value,value2,0);
ans=max(ans,value2);
#ifndef NDEBUG
cout<<"Add?< "<<value<<" f[i]="<<value2<<endl;
#endif
}
cout<<ans<<endl;
#ifndef NDEBUG
for (int i=1;i<=t.M*2;i++) if (t.t[0][i]) cout<<i<<':'<<t.t[0][i]<<' ';
cout<<endl;
#endif
}
return 0;
}
其实这题有更Easy的解法……贪心！
如果我们把原序列看成一条直线，且另a[0]和a[n+1]=-INF
那么如图所示
显然当最后的折现向下时：
显然解为凸点数*2
而当最后的折线向上时：
解为凸点数*2-1
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
#define MAXN (30000+10)
int tt,n,a[MAXN];
int main()
{
scanf("%d",&tt);
while (tt--)
{
scanf("%d",&n);
int ans=0;
a[0]=a[n+1]=-0xfffffff;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) if (a[i-1]<a[i]&&a[i]>a[i+1]) ans++;
ans*=2;
if (a[n-1]<a[n]) ans--;
cout<<ans<<endl;
}
return 0;
}
