QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#399062#8554. Bot FriendsBronyaWA 30ms3908kbC++14756b2024-04-25 21:19:422024-04-25 21:19:49

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 21:19:49]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:3908kb
  • [2024-04-25 21:19:42]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
char s[5005];
int dp[5005][5005];
int f[5005];
int main(){
	int T;
	scanf("%d",&T);
	int sb=0;
	while(T--){sb++;
		scanf("%s",s+1);
		int n=strlen(s+1); 
		for(int i=0;i<=n;i++)dp[i+1][i]=0;
		f[0]=0;
		for(int i=1;i<=n;i++){
			f[i]=n;
			for(int j=i;j>=1;j--){
				dp[j][i]=min(dp[j+1][i]+1,dp[j][i-1]+1);
				if(s[i]!='>'&&s[j]!='<')dp[j][i]=min(dp[j][i],dp[j+1][i-1]);
				f[i]=min(f[i],f[j-1]+1+dp[j][i]);
				f[i]=min(f[i],f[j-1]+1+dp[j][i-1]+(s[i]=='>'));
				f[i]=min(f[i],f[j-1]+1+dp[j+1][i]+(s[j]=='<'));
			}
		}
		if(sb==30){
			for(int i=1;i<=n;i++)putchar(s[i]);
			putchar('\n');
		}
//		printf("%d\n",dp[5][8]);
		if(T<=10)printf("%d\n",n-f[n]);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3908kb

input:

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 30ms
memory: 3872kb

input:

100000
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
>><>><<<<<
>?>?>?<<>>
?><?<<?<><
???><>?>?>
<??>?<<><?
??>><?<>>>
<><><?<>>?
?>>?>???><
?<?><?<<>?
>>><?<??><
><><<>?>?<
>?><>><<<?
>??>?><?<>
?????<><?>
<><<?<<>?<
><?>>?>?>?
?><><<<>>?
?<>?<>?<<<
<><<<<<>>>
?>?>?><<>>
<>?<>><>?<
<<<?<>>...

output:

>><<?<??>>
6
8
5
6
8
7
6
7
7
8
8

result:

wrong output format Expected integer, but ">><<?<??>>" found