UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214950#3856. 排序drdilyor20451ms5152kbC++111.1kb2024-11-24 12:24:552024-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