QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728019#8554. Bot FriendsfryanWA 69ms3700kbC++201.6kb2024-11-09 14:23:322024-11-09 14:23:45

Judging History

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

  • [2024-11-09 14:23:45]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:3700kb
  • [2024-11-09 14:23:32]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 500;

int n;
string s;
int dp[mxn][mxn][2];
//dp[x][x][0] = prev >
//dp[x][x][1] = prev <

int go(string &s) {
	n = sz(s);
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			dp[i][j][0] = -mxn*mxn;
			dp[i][j][1] = -mxn*mxn;
		}
	}
	dp[0][0][0] = 0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
//			if (dp[i][j][0] != -1) {
				if (s[i] != '<') {
					dp[i+1][j+1][0] = max(dp[i+1][j+1][0], dp[i][j][0]);
					dp[i+1][j+1][0] = max(dp[i+1][j+1][0], dp[i][j][1]);
				}
				if (s[i] != '>') {
					if (j) {
						dp[i+1][j-1][1] = max(dp[i+1][j-1][1], dp[i][j][0]+1);
						dp[i+1][j-1][1] = max(dp[i+1][j-1][1], dp[i][j][1]+2);
					} else {
						dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0]);
						dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][1]);
					}
					if (j >= 2) {
						dp[i+1][j-2][1] = max(dp[i+1][j-2][1], dp[i][j][0]+2);
						dp[i+1][j-2][1] = max(dp[i+1][j-2][1], dp[i][j][1]+3);
					}
				}
//			}
		}
	}
	
	int mx = 0;
	for (int i=0; i<=n; i++) {
		mx = max(mx, dp[n][i][0]);
		mx = max(mx, dp[n][i][1]);
		if (i) {
			mx = max(mx, dp[n][i][1]+1);
		}
	}
	return mx;
}

void solve() {
	cin>>s;
	int res = go(s);
	reverse(all(s));
	for (int i=0; i<sz(s); i++) {
		if (s[i]=='>') s[i]='<';
		else if (s[i]=='<') s[i]='>';
	}
	res = max(go(s),res);
	cout<<res<<"\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int t; cin>>t;
	while (t--) {
		solve();
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 69ms
memory: 3700kb

input:

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

output:

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

result:

wrong answer 7th numbers differ - expected: '6', found: '7'