QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#437914 | #8554. Bot Friends | liqingyang | TL | 591ms | 395824kb | C++17 | 1.1kb | 2024-06-09 19:55:35 | 2024-06-09 19:55:35 |
Judging History
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 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...