QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404349 | #8554. Bot Friends | yyyyxh | WA | 49ms | 1656kb | C++14 | 1003b | 2024-05-03 20:39:31 | 2024-05-03 20:39:33 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5003,INF=0x3f3f3f3f;
char s[N];
int n;
int f[N][N],g[N][N];
inline void chmn(int &x,int v){if(x>v) x=v;}
int id;
void solve(){
scanf("%s",s+1);
if(++id==30) printf("%s\n",s+1);
n=strlen(s+1);
for(int i=0;i<=n;++i)
for(int j=0;j<=i;++j) f[i][j]=g[i][j]=INF;
f[0][0]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<i;++j){
if(s[i]!='<'){
chmn(f[i][j+1],f[i-1][j]);
chmn(f[i][j],g[i-1][j]);
chmn(f[i][j],f[i-1][j]+1);
chmn(g[i][j],g[i-1][j]+1);
}
if(s[i]!='>'){
chmn(f[i][j],f[i-1][j]+1);
chmn(g[i][j],g[i-1][j]+1);
if(j) chmn(g[i][j],f[i-1][j]+1);
if(j>1) chmn(g[i][j-1],g[i-1][j]);
else if(j) chmn(f[i][0],g[i-1][j]);
if(j>1) chmn(g[i][j-1],f[i-1][j]+1);
else if(j) chmn(f[i][0],f[i-1][j]+1);
}
}
printf("%d\n",n-min(f[n][0],g[n][1]));
}
int main(){
int tc;
scanf("%d",&tc);
while(tc--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 1656kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 49ms
memory: 1652kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 8 6 7 6 7 6 6 8 7 8 7 8 7 7 6 6 7 7 2 6 6 3 9 6 >><<?<??>> 5 5 7 5 8 7 6 8 7 7 6 6 7 4 2 7 6 8 7 8 6 6 5 7 8 8 8 8 7 5 6 7 7 6 8 7 6 8 6 7 8 7 7 6 8 5 7 6 6 5 5 7 7 6 4 8 6 6 7 5 7 6 7 7 8 3 8 8 7 8 7 7 4 8 8 7 5 8 7 7 8 8 7 5 7 8 5 7 6 5 8 8 7 7 8 6 7 8 6 6 8 7 8 7 6 6 5 7 8 6 8 6 7 5 7 4...
result:
wrong output format Expected integer, but ">><<?<??>>" found