ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214952 | #3856. 排序 | drdilyor | 0 | 135ms | 5152kb | C++11 | 1.1kb | 2024-11-24 12:32:39 | 2024-11-24 13:16:04 |
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;
dp[cur][j][k]=max(dp[cur][j][k],dp[lst][j][k]);
if(a[i]>j){
dp[cur][a[i]][j]=max(dp[cur][a[i]][j],dp[lst][j][k]+1);
}
else{
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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 135ms
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:
27
result:
wrong answer 1st numbers differ - expected: '11', found: '27'
Subtask #2:
score: 0
Skipped
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