QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#437914#8554. Bot FriendsliqingyangTL 591ms395824kbC++171.1kb2024-06-09 19:55:352024-06-09 19:55:35

Judging History

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

  • [2024-06-09 19:55:35]
  • 评测
  • 测评结果:TL
  • 用时:591ms
  • 内存:395824kb
  • [2024-06-09 19:55:35]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
inline void Max(int &x,int y)
{
	x=x>y?x:y;
}
int T,n,f[5010][5010][2],g[5010][5010][2];
char s[5010];
inline void dp()
{
	f[0][0][1]=-1e9;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=i+1;j++)
		{
			f[i+1][j][0]=f[i+1][j][1]=-1e9;
		}
		for(int j=0;j<=i;j++)
		{
			for(int k=0;k<2;k++)
			{
				int v=f[i][j][k];
				if(j)
				{
					if(s[i+1]!='>')
					{
						Max(f[i+1][j-1][0],v+1+(!k));
					}
					if(s[i+1]!='<')
					{
						Max(f[i+1][j][1],v+(!k));
					}
				}
				if(s[i+1]!='>')
				{
					Max(f[i+1][j][0],v);
				}
				if(s[i+1]!='<')
				{
					Max(f[i+1][j+1][1],v);
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>s+1;
		n=strlen(s+1);
		dp(),reverse(s+1,s+n+1);
		for(int i=1;i<=n;i++)
		{
			s[i]=(s[i]=='?')?'?'
			:(s[i]=='<'?'>':'<');
		}
		swap(f,g),dp(),swap(f,g);
		int ans=0;
		for(int i=0;i<=n;i++)
		{
			Max(ans,f[i][0][0]+g[n-i][0][0]);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 591ms
memory: 395824kb

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

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

output:


result: