http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1475
思路:以a[i]为Wavio Sequence的最大值,(根据定义)计算从0到i和从i到n的lis长度的较小者,为以a[i]为最大值的Wavio Sequence的半长度,最后取所有半长度的最大值*2-1
完整代码:
/*0.102s*/
#include<bits/stdc++.h>
using namespace std;
const int mx = 10005;
int a[mx], d[2][mx], lis[mx];
int main()
{
int N, len, i, j, ans;
while (~scanf("%d", &N))
{
len = 0;
for (i = 1; i <= N; ++i)
{
scanf("%d", &a[i]);
d[0][i] = j = lower_bound(lis + 1, lis + len + 1, a[i]) - lis;
len = max(len, j);
lis[j] = a[i];
}
len = 0;
for (i = N; i; --i)
{
d[1][i] = j = lower_bound(lis + 1, lis + len + 1, a[i]) - lis;
len = max(len, j);
lis[j] = a[i];
}
ans = 0;
for (i = 1; i <= N; ++i)
ans = max(ans, (min(d[0][i], d[1][i]) << 1) - 1);
printf("%d\n", ans);
}
return 0;
}