QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721498#8554. Bot Friendslzc0115WA 52ms5700kbC++141.1kb2024-11-07 16:15:282024-11-07 16:15:28

Judging History

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

  • [2024-11-07 16:15:28]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:5700kb
  • [2024-11-07 16:15:28]
  • 提交

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'