74 条题解

  • 2
    @ 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
    @ 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);
    }
    
  • 1
    @ 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);

    }

  • 1
    @ 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
    @ 2015-08-17 20:33:11

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

  • 0
    @ 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
    @ 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
    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
    @ 2014-08-12 19:55:49

    参照P1686。。

  • 0
    @ 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
    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
    @ 2014-03-01 00:15:55

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

  • 0
    @ 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
    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
    @ 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];

  • 0
    @ 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;
    }

  • 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

  • 0
    @ 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
    @ 2010-04-06 21:08:09

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

  • 0
    @ 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
    @ 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)。。最长条件子序列。。

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

    有一个问题请教一下。

    我让f,f=1

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

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

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

    这是为什么呢?

  • 0
    @ 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

    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

信息

ID
1571
难度
4
分类
动态规划 | 动态规划 | LIS 点击显示
标签
递交数
1788
已通过
693
通过率
39%
被复制
1
上传者