ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395 | #57. 「NOIP2013」花匠 | ryp | 80 | 128ms | 4584kb | C++14 | 1.7kb | 2025-04-23 12:47:43 | 2025-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...