74 条题解
-
2
program543 LV 8 @ 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; } -
1
#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);}
-
1
2015030402015 LV 6 @ 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;
} -
0
wangzhongtao LV 9 @ 2015-08-17 20:33:11
O(n^2)可以过，不用担心超时。话说第一次交的时候数据范围少写了个0，RE一次☄ฺ(◣д◢)☄ฺ
-
0
xxxxxxxxyu LV 8 @ 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;}
想了好久，可算想到简便的算法啦 -
0
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
read(n);
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. -
0
ksws0305545 LV 8 @ 2014-08-12 19:55:49
参照P1686。。
-
0
朴素的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
Linking foo.exe
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 -
0
program flower;
var i,j,x,n,s:longint;
a,b:array[0..100000] of longint;
c:array[0..100000] of boolean;
begin
readln(n);
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. -
0
最长序列，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;
} -
0
wjt_silent LV 8 @ 2012-08-13 16:28:03
实质：在一个序列里找到上下起伏的数的个数
var i,j,n:longint;
a,f:array[1..10001]of longint;begin
readln(n);
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] -
0
gallenvara LV 7 @ 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好丑！！
-
0
编译通过...
├ 测试数据 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)。。最长条件子序列。。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar
n,i,x,k,y:longint;
begin
readln(n);
read(y);
x:=y;
k:=1;
for i:=2 to n do
begin
read(y);
if ((k and 1=0)and(y>x))or((k and 1=1)and(y
program543
LV 8
@ 2017-09-23 09:59:16
