QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721498 | #8554. Bot Friends | lzc0115 | WA | 52ms | 5700kb | C++14 | 1.1kb | 2024-11-07 16:15:28 | 2024-11-07 16:15:28 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int T, n, f[5010][5010][2], ans;
string s;
int main(){
cin >> T;
while(T--){
ans = -1e9;
cin >> s;
n = s.size();
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
f[i][j][0] = f[i][j][1] = -1e9;
}
}
f[0][0][1] = 0;
for(int i = 1; i <= n; i++){
if(s[i - 1] != '>') f[i][0][1] = f[i - 1][0][1];
if(s[i - 1] != '<') f[i][1][0] = f[i - 1][0][1];
for(int j = 1; j < i; j++){
if(s[i - 1] != '<'){
f[i][j][0] = max(f[i][j][0], f[i - 1][j][1] + 1);
f[i][j + 1][0] = max(f[i][j + 1][0], f[i - 1][j][0]);
}
if(s[i - 1] != '>'){
f[i][j][1] = max(f[i][j][1], f[i - 1][j][0]);
f[i][j - 1][1] = max(f[i][j - 1][1], max(f[i - 1][j][1] + 2, f[i - 1][j][0] + 1));
}
}
}
for(int i = 0; i <= n; i++){
ans = max(ans, max(f[n][i][0], f[n][i][1] + (i > 0)));
}
cout << ans << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5700kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 52ms
memory: 3728kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 7 6 6 6 7 6 5 8 6 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 5 8 7 8 5 6 5 7 8 8 8 8 7 5 5 7 7 6 8 7 5 8 6 6 8 7 7 6 8 5 7 6 6 5 5 7 7 5 3 8 6 5 7 5 7 6 7 7 8 3 8 8 7 8 7 7 4 8 8 7 5 8 6 7 7 8 7 5 7 8 5 7 6 5 8 8 7 7 8 6 7 8 6 6 8 7 8 7 6 5 5 7 8 6 8 6 7 5 7 4 6 6 7 7 7 ...
result:
wrong answer 6th numbers differ - expected: '8', found: '7'