Logo Wy Online Judge

WyOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#395#57. 「NOIP2013」花匠ryp80128ms4584kbC++141.7kb2025-04-23 12:47:432025-04-23 12:47:43

answer

#include<iostream>
#include<cstdio>
#define II int
#define R register
#define I 123456
using namespace std;


II a[I],d_1[I],d_2[I];

II n;


int main()
{
//  freopen("FlowerNOIP2013.in","r",stdin);
//  freopen("FlowerNOIP2013.out","w",stdout);
    scanf("%d",&n);
    R II x;
    for(R II i=1;i<=n;i++) scanf("%d",&x), a[i]=x;
    d_1[1]=d_2[1]=1;
    //d_1[]代表的是当前元素是以当前元素为中心的三个相邻的元素中最大的;
    //同理,d_2[]代表的是当前元素是以当前元素为中心的三个相邻的元素中最小的;
    //但是当前元素不一定选,可能是继承上一个元素的信息;
    for(R II i=2;i<=n;i++)
    {
        if(a[i]>a[i-1]) d_1[i]=max(d_1[i-1],d_2[i-1]+1), d_2[i]=d_2[i-1];
        //如果当前元素大于这个前一个元素;
        //那么当前元素若果选,则是前一个元素作为最低点时的长度+1;
        //如果不选,就继承前一个元素作为最高点,等价于当前元素作为最高点;
        //当前元素作为最低点就只能继承前一个点作为最低点;
            else{
                if(a[i]<a[i-1]) d_1[i]=d_1[i-1], d_2[i]=max(d_1[i-1]+1,d_2[i-1]);
                //如果当前元素小于前一个元素,则道理同上,只是反过来;
                    else d_1[i]=d_1[i-1],   d_2[i]=d_2[i-1];
                    //如果当前元素等于前一个元素,那么这个元素直接继承前一个元素的所有信息;
                    //因为这两个点是完全等价的;
            }
    }
    R II ans=max(d_1[n],d_2[n]);
    //我们在最后时取两种状态的最大值作为答案;
    cout<<ans<<endl;
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 3ms
memory: 3540kb

input:

5
1 3 9 5 10

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 5
Accepted
time: 1ms
memory: 3536kb

input:

10
1 83 31 100 68 53 40 81 66 0

output:

7

result:

ok 1 number(s): "7"

Test #3:

score: 5
Accepted
time: 3ms
memory: 3672kb

input:

25
6 13 37 5 15 3 56 31 43 24 9 32 31 57 54 44 17 55 76 48 37 0 62 20 79

output:

18

result:

ok 1 number(s): "18"

Test #4:

score: 5
Accepted
time: 3ms
memory: 3352kb

input:

100
122 50 454 694 255 733 942 678 77 410 619 522 371 99 404 481 321 934 742 140 337 378 586 246 893...

output:

65

result:

ok 1 number(s): "65"

Test #5:

score: 5
Accepted
time: 3ms
memory: 3356kb

input:

300
237 62 871 369 447 246 805 24 471 917 947 771 592 432 608 598 229 849 345 880 905 706 78 564 788...

output:

227

result:

ok 1 number(s): "227"

Test #6:

score: 5
Accepted
time: 3ms
memory: 3480kb

input:

500
933 465 296 790 215 248 887 529 335 473 881 249 729 817 149 596 509 4 156 837 416 387 971 639 39...

output:

333

result:

ok 1 number(s): "333"

Test #7:

score: 5
Accepted
time: 3ms
memory: 3348kb

input:

1000
4 4 8 0 7 8 4 1 9 9 8 8 10 9 1 5 8 3 5 5 3 5 4 1 9 9 4 8 7 9 5 9 2 5 2 7 9 8 0 3 4 7 5 0 3 8 2 ...

output:

615

result:

ok 1 number(s): "615"

Test #8:

score: 5
Accepted
time: 2ms
memory: 3724kb

input:

10000
799 103 129 391 924 738 527 63 289 320 184 51 431 818 708 322 583 569 956 96 187 162 530 420 2...

output:

6634

result:

ok 1 number(s): "6634"

Test #9:

score: 5
Accepted
time: 15ms
memory: 3928kb

input:

50000
342331 545532 945559 676659 351871 221830 479525 667721 599012 832200 756681 66598 185604 5798...

output:

33401

result:

ok 1 number(s): "33401"

Test #10:

score: 5
Accepted
time: 27ms
memory: 4512kb

input:

100000
756532 355817 558894 863352 870275 50258 757128 984173 364605 636708 891605 956353 346613 220...

output:

66745

result:

ok 1 number(s): "66745"

Test #11:

score: 5
Accepted
time: 2ms
memory: 3672kb

input:

10
24 84 99 9 20 21 47 68 4 52

output:

6

result:

ok 1 number(s): "6"

Test #12:

score: 5
Accepted
time: 3ms
memory: 3552kb

input:

25
190 78 298 42 194 202 33 86 3 261 190 163 129 200 38 68 122 150 295 241 183 143 36 73 57

output:

16

result:

ok 1 number(s): "16"

Test #13:

score: 5
Accepted
time: 2ms
memory: 3548kb

input:

824
684 947 725 881 108 44 219 288 140 272 749 454 772 135 884 662 196 209 957 982 107 693 169 120 5...

output:

556

result:

ok 1 number(s): "556"

Test #14:

score: 5
Accepted
time: 0ms
memory: 3552kb

input:

853
438 662 172 259 136 348 799 174 461 391 122 312 289 933 506 990 133 178 244 68 545 942 498 560 1...

output:

580

result:

ok 1 number(s): "580"

Test #15:

score: 5
Accepted
time: 32ms
memory: 4580kb

input:

94233
524975 999845 606671 355917 808085 708019 924944 470180 408114 878240 201435 505120 784577 816...

output:

62687

result:

ok 1 number(s): "62687"

Test #16:

score: 5
Accepted
time: 26ms
memory: 4584kb

input:

100000
9954 8912 9578 8522 1414 9293 7627 4573 2539 2531 2610 1023 4434 2429 3283 2073 6474 6303 494...

output:

66844

result:

ok 1 number(s): "66844"

Test #17:

score: 0
Runtime Error

input:

358644
405856 2143009 9629001 1385904 7919178 2823295 9011235 6087312 1896159 3876274 8061907 550771...

output:


result:


Test #18:

score: 0
Runtime Error

input:

1080882
32848795 54032797 21791400 10508059 11788690 15561510 42103456 43549942 72588502 48274324 11...

output:


result:


Test #19:

score: 0
Runtime Error

input:

1706754
19484564 493097243 314337313 294463439 198535527 222946858 226379950 454834276 364658823 327...

output:


result:


Test #20:

score: 0
Runtime Error

input:

2000000
989559694 310396286 206665161 878091432 101608224 199512451 237785845 850397217 916915833 21...

output:


result: