# 74 条题解

• @ 2017-09-23 09:59:16
``````#include <stdio.h>
#include <iostream>
using namespace std;
int n;
int a[10001];
int f[10001];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=1;
}
for (int i=1;i<=n;i++)
for (int j=1;j<i;j++)
if ((f[j]%2==1&&a[i]<a[j])||(f[j]%2==0&&a[i]>a[j]))
f[i]=max(f[i],f[j]+1);
int temp=0;
for (int i=1;i<=n;i++)
temp=max(temp,f[i]);
printf("%d",temp);
return 0;
}
``````
• @ 2020-01-17 10:49:43
``````#include<stdio.h>
int a[10005];
int main(){
int n,now,odd,even,i;
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
now=1;
odd=a[1];
for (i=2;i<=n;i++) {
if (now%2==1) {
if (a[i]<odd) now++; }
else
{ if (a[i]>odd) now++;}
odd=a[i];
}
printf("%d\n",now);
}
``````
• @ 2017-08-29 21:15:40

#include<stdio.h>
int a[10005];
int main(){
int n,now,odd,even,i;
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
now=1;
odd=a[1];
for (i=2;i<=n;i++) {
if (now%2==1) {//下一个放小的
if (a[i]<odd) now++; }
else //下一个放大的
{ if (a[i]>odd) now++;}
odd=a[i];
}
printf("%d\n",now);

}

• @ 2016-03-24 13:00:40

O(n)算法，AC

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 10000 + 10;
int a[maxn], b[maxn];

int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
int ans = 1;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
b[1] = a[1];
for (int j = 2; j <= n; j++)
{
if (ans % 2)
{
if (a[j] >= b[ans]) b[ans] = a[j];
else b[++ans] = a[j];
}
else
{
if (a[j] <= b[ans]) b[ans] = a[j];
else b[++ans] = a[j];
}
}
printf("%d\n", ans);
}
return 0;
}

• @ 2015-08-17 20:33:11

O(n^2)可以过，不用担心超时。话说第一次交的时候数据范围少写了个0，RE一次☄ฺ(◣д◢)☄ฺ

• @ 2015-08-11 18:40:47

#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int yu[10000],f[10000];
int sum;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>yu[i];
}
for(int i=1;i<=n;i++){

for(int j=i;j<=n;j++)
{
if(f[i]%2==0)
{
if(yu[j]<yu[i])f[j]=max(f[i]+1,f[j]);
}
else if(f[i]%2==1)
{
if(yu[j]>yu[i])f[j]=max(f[i]+1,f[j]);
}
}
}
int maxn=0;
for(int i=1;i<=n;i++){
maxn=max(maxn,f[i]);
}
cout<<maxn+1;
return 0;

}
想了好久，可算想到简便的算法啦

• @ 2014-08-15 23:58:57

vj真快啊。。。这TM都过了
program p1571;
var a:array[0..10000] of longint;
f:array[0..10000,1..2] of longint;
n,i,j,sum:longint;
//
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
//
begin
for i:=1 to n do read(a[i]);
for i:=1 to n do f[i,1]:=1;
for i:=1 to n do
begin
for j:=1 to i-1 do if (a[i]>a[j]) and (f[j,2]<>0) then f[i,1]:=max(f[j,2]+1,f[i,1]);
for j:=1 to i-1 do if (a[i]<a[j]) and (f[j,1]<>0) then f[i,2]:=max(f[j,1],f[i,2]);
end;
for i:=1 to n do
for j:=1 to 2 do sum:=max(sum,(f[i,j]-1)*2+j);
write(sum);
end.

• @ 2014-08-12 19:55:49

参照P1686。。

• @ 2014-07-16 20:05:12

朴素的dp+朴素的优化，求教怎样离散化+线段树AC
评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
28 lines compiled, 0.1 sec , 28400 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 15 ms, mem = 936 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 936 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 936 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 936 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 936 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 936 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 936 KiB, score = 10
Accepted, time = 60 ms, mem = 940 KiB, score = 100

• @ 2014-03-01 00:15:55

与2013noip day2 T2 惊人的相似 改了个初始值就AC了

• @ 2014-03-01 00:12:08

program flower;
var i,j,x,n,s:longint;
a,b:array[0..100000] of longint;
c:array[0..100000] of boolean;
begin
for i:=1 to n do read(b[i]);
s:=0;
for i:=1 to n do c[i]:=true;
for i:=1 to n do
if b[i]=b[i+1] then c[i]:=false;
for j:=1 to n do
if c[j] then
begin
s:=s+1;
a[s]:=b[j];
end;
x:=s;a[0]:=0;
for i:=1 to x-1 do
if not (((a[i-1]<a[i]) and (a[i+1]<a[i])) or ((a[i-1]>a[i]) and (a[i+1]>a[i])))
then x:=x-1;
write(x);
end.

• @ 2013-10-28 19:50:46

这题很水但代码很优美

for i:=2 to n do
if (ans and 1=1) then
if (a[i]<f[ans]) then
begin inc(ans); f[ans]:=a[i]; end
else f[ans]:=a[i]
else if (a[i]>f[ans]) then
begin inc(ans); f[ans]:=a[i]; end
else f[ans]:=a[i];

• @ 2013-10-24 14:26:08

最长序列，O(n^2)

f[i]=max{f[j]+1}, 1<=j<i, f[j]+1是奇数: a[j]<a[i]; 偶数: a[j]>a[i]

#include <iostream>

using namespace std;

const int MAX_SIZE = 10000;

int a[MAX_SIZE + 1], f[MAX_SIZE + 1];

int main()
{
int N;
cin >> N;

int i, j;
for (i = 1; i <= N; i++) {
cin >> a[i];
}

f[1] = 1;
for (i = 2; i <= N; i++) {
f[i] = 1;
for (j = i - 1; j >= 1; j--) {
if ((f[j] + 1) % 2 != 0) {
if (f[i] < f[j] + 1 && a[j] < a[i]) f[i] = f[j] + 1;
} else {
if (f[i] < f[j] + 1 && a[j] > a[i]) f[i] = f[j] + 1;
}
}
}

cout << f[N];

return 0;
}

• @ 2013-08-16 18:38:08

easy
08-11 Accepted
08-11 Accepted
08-11 Accepted
08-11 Accepted
08-11 Accepted
08-11 Accepted
08-11 Accepted

• @ 2012-08-13 16:28:03

实质：在一个序列里找到上下起伏的数的个数

var i,j,n:longint;

a,f:array[1..10001]of longint;

begin

for i:=1 to n do read(a[i]);

f[1]:=a[1]; j:=1;

for i:=2 to n do

begin

if (j mod 2=1)and(a[i]>f[j]) then f[j]:=a[i];

if (j mod 2=1)and(a[i]

• @ 2010-04-06 21:08:09

Orz以下各神new!!!!!树状数组果断秒。。

• @ 2009-10-31 20:10:45

├ 测试数据 01：答案正确... 556ms

├ 测试数据 02：答案正确... 353ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 228ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 447ms

├ 测试数据 10：答案正确... 353ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2087ms

好丑！！

• @ 2009-10-30 23:57:42

编译通过...

├ 测试数据 01：答案正确... 447ms

├ 测试数据 02：答案正确... 197ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 88ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 291ms

├ 测试数据 10：答案正确... 212ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1276ms

碰上easy。。什么叫没效率。。O(n^2)。。最长条件子序列。。

• @ 2009-10-29 19:53:50

有一个问题请教一下。

我让f,f=1

循环i=2..n j=1..i

可是这样只有50分 有5个点比正确答案多一

可是把循环改成i=1..n j=0..i-1后就通过了

这是为什么呢？

• @ 2009-10-30 13:13:31

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

n,i,x,k,y:longint;

begin

x:=y;

k:=1;

for i:=2 to n do

begin

if ((k and 1=0)and(y>x))or((k and 1=1)and(y

ID
1571

4

1788

693

39%

1