ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214950 | #3856. 排序 | drdilyor | 20 | 451ms | 5152kb | C++11 | 1.1kb | 2024-11-24 12:24:55 | 2024-11-24 13:15:55 |
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
int n=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
int n;
int a[500005];
int dp[2][505][505];
signed main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
memset(dp,-0x3f,sizeof(dp));
dp[1][a[1]][0]=1;
for(int i=2;i<=n;i++){
int lst=(i&1)^1;
int cur=i&1;
for(int j=1;j<=n;j++){
for(int k=0;k<=n;k++){
if(dp[lst][j][k]<0)continue;
if(a[i]>j){
dp[cur][a[i]][j]=max(dp[cur][a[i]][j],dp[lst][j][k]+1);
}
else{
dp[cur][j][k]=max(dp[cur][j][k],dp[lst][j][k]);
if(a[i]>k){
dp[cur][a[i]][k]=max(dp[cur][a[i]][k],dp[lst][j][k]);
}
}
}
}
for(int j=1;j<=n;j++)for(int k=0;k<=n;k++)dp[lst][j][k]=-(1ll<<60);
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++)res=max(res,dp[n&1][i][j]);
}
cout<<res<<"\n";
return 0;
}
//look at my code
//my code is amazing
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 119ms
memory: 5152kb
input:
475 319 474 473 472 471 183 108 346 43 466 465 464 168 462 461 309 459 458 457 456 455 38 372 312 94...
output:
11
result:
ok 1 number(s): "11"
Test #2:
score: 0
Accepted
time: 110ms
memory: 5148kb
input:
469 96 407 467 466 240 146 463 462 119 261 459 304 266 456 385 454 453 452 79 450 133 400 447 123 21...
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 116ms
memory: 5152kb
input:
492 139 64 490 25 488 61 486 133 167 483 482 124 88 479 100 220 476 475 474 90 112 273 470 16 468 46...
output:
17
result:
ok 1 number(s): "17"
Test #4:
score: 0
Accepted
time: 106ms
memory: 5148kb
input:
480 480 479 328 477 410 112 125 44 472 26 470 469 468 24 92 342 68 463 462 191 460 459 62 457 114 45...
output:
19
result:
ok 1 number(s): "19"
Subtask #2:
score: 0
Runtime Error
Test #5:
score: 0
Runtime Error
input:
3838 27 26 25 24 23 22 21 20 19 18 17 16 997 14 3442 12 11 10 9 8 7 2498 5 4 3 2 1 2834 2833 2832 28...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #9:
score: 0
Runtime Error
input:
499758 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 ...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
input:
466818 447360 121353 327541 289718 71942 242279 307652 438765 78054 253024 190170 21720 292462 72832...
output:
result:
Subtask #5:
score: 0
Skipped