QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554363#8554. Bot Friendsucup-team1231#TL 292ms3964kbC++142.1kb2024-09-09 10:42:532024-09-09 10:42:54

Judging History

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

  • [2024-09-09 10:42:54]
  • 评测
  • 测评结果:TL
  • 用时:292ms
  • 内存:3964kb
  • [2024-09-09 10:42:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
typedef long long int LLI;
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

char s[5001];
int dp[2][5001][2];
int pre[10005],suff[10005];
int main() {
    int i,j,k;
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%s",s);
        n = strlen(s);

        auto f = [&](int *arr) {
            for (i = 0; i <= n; i++) dp[0][i][0] = dp[0][i][1] = 1e9;
            dp[0][1][1] = 0;
            arr[0] = 0;
            for (i = 1; i <= 2*n; i++) {
                for (j = 0; j <= n; j++) {
                    for (k = 0; k < 2; k++) dp[i & 1][j][k] = 1e9;
                }
                for (j = 0; j <= n; j++) {
                    for (k = 0; k < 2; k++) {
                        if (dp[(i-1) & 1][j][k] < 1e9) {
                            if (i & 1) {
                                if (s[(i-1)/2] != '>') {
                                    if (j > 0) dp[i&1][j-1][0] = min(dp[i&1][j-1][0],dp[(i-1)&1][j][k]+k);
                                }
                                if (s[(i-1)/2] != '<') {
                                    if (j < n) dp[i&1][j+1][1] = min(dp[i&1][j+1][1],dp[(i-1)&1][j][k]);
                                }
                            }
                            else {
                                if (j > 0) dp[i&1][j-1][0] = min(dp[i&1][j-1][0],dp[(i-1)&1][j][k]+k);
                                if (j < n) dp[i&1][j+1][1] = min(dp[i&1][j+1][1],dp[(i-1)&1][j][k]);
                            }
                        }
                    }
                }
                arr[i+1] = dp[i & 1][0][0];
            }
        };
        f(pre);
        reverse(s,s+n);
        for (i = 0; i < n; i++) {
            if (s[i] == '<') s[i] = '>';
            else if (s[i] == '>') s[i] = '<';
        }
        f(suff);
        reverse(suff,suff+2*n+1);
        int ans = 1e9;
        for (i = 0; i <= 2*n; i += 2) {
            ans = min(ans,pre[i]+suff[i]);
        }
        printf("%d\n",n-ans);
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3896kb

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 292ms
memory: 3964kb

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
6
5
7
5
8
7
6
8
7
8
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
8
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
6
6
7
7
7
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 280ms
memory: 3808kb

input:

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

output:

2
8
8
5
7
3
7
6
6
5
6
4
8
8
4
6
2
8
4
6
4
6
3
7
8
8
3
4
5
7
5
8
7
6
5
6
5
5
6
6
5
7
3
4
7
6
6
5
8
7
5
3
6
4
6
6
3
4
6
6
8
6
6
6
7
4
4
6
6
6
1
5
4
7
6
5
6
4
4
4
5
5
4
6
8
7
4
6
4
4
5
4
7
8
6
6
6
6
4
7
5
6
4
6
6
7
4
2
5
5
6
5
6
6
5
6
4
4
3
8
5
7
5
6
6
6
5
5
7
8
7
5
4
4
5
6
7
5
3
5
5
3
7
7
2
7
6
8
7
2
...

result:

ok 100000 numbers

Test #4:

score: -100
Time Limit Exceeded

input:

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

output:

15
17
12
12
14
13
15
17
15
14
15
15
13
16
15
16
15
15
17
15
15
10
16
12
14
16
17
16
11
14
13
14
13
14
14
10
12
11
15
13
16
13
13
13
16
10
14
16
12
12
13
14
14
16
17
13
15
15
11
17
15
15
16
15
17
15
16
14
14
13
11
15
14
17
15
17
17
15
13
17
16
16
16
14
17
14
12
14
13
15
16
12
15
16
14
15
13
16
15
14
...

result: