QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474362#8554. Bot Friendsreal_sigma_team#WA 89ms3852kbC++201.5kb2024-07-12 17:39:152024-07-12 17:39:15

Judging History

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

  • [2024-07-12 17:39:15]
  • 评测
  • 测评结果:WA
  • 用时:89ms
  • 内存:3852kb
  • [2024-07-12 17:39:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define x first
#define y second

void solve();

int main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif
	cout << fixed << setprecision(30);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

const int N = 5000;

int dp[N][N][3]; //0 - mid, 1 - left, 2 - right


void solve() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			for (int c = 0; c < 3; ++c) {
				dp[i][j][c] = -1e9;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (s[i] != '<') {
			dp[i][i][2] = 0;
		}
		if (s[i] != '>') {
			dp[i][i][1] = 0;
		}
	}
	for (int len = 1; len < n; ++len) {
		for (int l = 0, r = len; r < n; ++l, ++r) {
			if (s[l] != '<') {
				for (int c = 0; c < 3; ++c) {
					dp[l][r][1] = max(dp[l][r][1], dp[l + 1][r][c] + (c != 1));
				}
			}
			if (s[l] != '>') {
				for (int c = 0; c < 3; ++c) {
					int q = (c == 2 ? 2 : 0);
					dp[l][r][q] = max(dp[l][r][q], dp[l + 1][r][c]);
				}
			}
			if (s[r] != '<') {
				for (int c = 0; c < 3; ++c) {
					int q = (c == 1 ? 1 : 0);
					dp[l][r][q] = max(dp[l][r][q], dp[l][r - 1][c]);
				}
			}
			if (s[r] != '>') {
				for (int c = 0; c < 3; ++c) {
					dp[l][r][2] = max(dp[l][r][2], dp[l][r - 1][c] + (c != 2));
				}
			}
		}
	}
	vector<int> dp2(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			for (int c = 0; c < 3; ++c) {
				dp2[j + 1] = max(dp2[j + 1], dp2[i] + dp[i][j][c]);
			}
		}
	}
	cout << dp2.back() << '\n';
}

详细

Test #1:

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

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 89ms
memory: 3660kb

input:

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

output:

8
7
8
5
6
8
8
7
6
7
7
6
8
7
8
7
8
7
7
6
7
7
7
5
7
6
5
9
7
7
5
7
7
9
7
6
8
7
7
8
7
7
6
4
7
7
8
7
9
6
7
6
7
8
8
8
8
7
6
7
7
7
7
8
8
7
8
6
7
8
7
7
7
8
6
7
7
7
5
6
7
8
7
6
8
7
7
7
6
7
7
7
7
8
6
8
9
7
8
7
7
6
8
8
6
6
8
7
7
8
8
7
5
7
8
6
7
7
7
8
8
7
7
8
8
8
8
7
7
8
7
8
7
6
7
6
6
8
7
8
7
7
6
7
7
7
7
7
7
8
...

result:

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