QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#474397 | #8554. Bot Friends | real_sigma_team# | WA | 89ms | 3692kb | C++20 | 1.6kb | 2024-07-12 17:50:23 | 2024-07-12 17:50:24 |
Judging History
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][1] = 0;
}
if (s[i] != '>') {
dp[i][i][2] = 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));
}
}
// cout << l << ' ' << r;
// for (int c = 0; c < 3; ++c) cout << ' ' << dp[l][r][c];
// cout << endl;
}
}
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: 3692kb
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: 3636kb
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 5 5 7 5 8 7 6 8 7 7 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 7 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 7 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:
wrong answer 30th numbers differ - expected: '6', found: '5'