QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390014#8554. Bot Friendsucup-team1191WA 322ms3712kbC++209.0kb2024-04-14 23:58:252024-04-14 23:58:25

Judging History

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

  • [2024-04-14 23:58:25]
  • 评测
  • 测评结果：WA
  • 用时：322ms
  • 内存：3712kb
查看
  • [2024-04-14 23:58:25]
  • 提交

answer

// !!!!!!
// rename to template.cpp instead of main.cpp
#include <bits/stdc++.h>

#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
                    .time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
template<typename T, typename U>
ostream& operator << (ostream& o, const pair<T, U>& p) {
    return o << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator << (ostream& o, const vector<T>& v) {
    bool first = true;
    o << "[";
    for (const auto& l : v) {
        if (!first) o << ", ";
        o << l;
        first = false;
    }
    return o << "]";
}
template<typename T>
ostream& operator << (ostream& o, const set<T>& v) {
    bool first = true;
    o << "{";
    for (const auto& l : v) {
        if (!first) o << ", ";
        o << l;
        first = false;
    }
    return o << "}";
}
#ifdef ONPC
#define show(x) cout << "LINE " << __LINE__ << ": " << #x << "=" << x << std::endl;
#else
#define show(x) 42
#endif

using ll = long long;
using ld = double;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    const int inf = 1e9;
    vector<vector<array<int, 3>>> dp(n, vector<array<int, 3>>(n, {inf, inf, inf}));
    // {left, middle, right}
    for (int i = 0; i < n; ++i) {
        if (s[i] == '<') {
            dp[i][i][2] = 1;
        } else if (s[i] == '>') {
            dp[i][i][0] = 1;
        } else {
            dp[i][i][0] = dp[i][i][2] = 1;
        }
    }
    vector<vector<array<int, 5>>> opt(n, vector<array<int, 5>>(n, {-1, -1, -1, -1, -1}));
    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l < n; ++l) {
            int r = l + len - 1;
            if (r >= n) break;
            {
                int L = l;
                int R = r - 1;
                if (len > 2) {
                    L = opt[l][r - 1][0];
                    R = opt[l + 1][r][0];
                    if (L == -1 || R == -1) {
                        L = l; R = r - 1;
                    }
                    L = max(L, l);
                    R = min(R, r - 1);
                }
                if (R < L) R = L;
                // L = l; R = r - 1;
                //L = max(l, L - 10);
                //R = min(r - 1, R + 10);
                for (int m = L; m <= R; ++m) {
                    if (dp[l][r][0] > dp[l][m][0] + dp[m + 1][r][0]) {
                        dp[l][r][0] = dp[l][m][0] + dp[m + 1][r][0];
                        opt[l][r][0] = m;
                    }
                }
            }
            {
                int L = l;
                int R = r - 1;
                if (len > 2) {
                    L = opt[l][r - 1][1];
                    R = opt[l + 1][r][1];
                    if (L == -1 || R == -1) {
                        L = l; R = r - 1;
                    }
                    L = max(L, l);
                    R = min(R, r - 1);
                }
                if (R < L) R = L;
                // L = l; R = r - 1;
                //L = max(l, L - 10);
                //R = min(r - 1, R + 10);
                int opt_val = 1e9;
                for (int m = L; m <= R; ++m) {
                    int cur = dp[l][m][1] + dp[m + 1][r][0];
                    if (opt_val > cur) {
                        opt_val = cur;
                        opt[l][r][1] = m;
                    }
                }
                dp[l][r][1] = min(dp[l][r][1], opt_val);
            }
            {
                int L = l;
                int R = r - 1;
                if (len > 2) {
                    L = opt[l][r - 1][2];
                    R = opt[l + 1][r][2];
                    if (L == -1 || R == -1) {
                        L = l; R = r - 1;
                    }
                    L = max(L, l);
                    R = min(R, r - 1);
                }
                if (R < L) R = L;
                // L = l; R = r - 1;
                //L = max(l, L - 10);
                //R = min(r - 1, R + 10);
                int opt_val = 1e9;
                for (int m = L; m <= R; ++m) {
                    int cur = dp[l][m][2] + dp[m + 1][r][1];
                    if (opt_val > cur) {
                        opt_val = cur;
                        opt[l][r][2] = m;
                    }
                }
                dp[l][r][1] = min(dp[l][r][1], opt_val);
            }
            {
                int L = l;
                int R = r - 1;
                if (len > 2) {
                    L = opt[l][r - 1][3];
                    R = opt[l + 1][r][3];
                    if (L == -1 || R == -1) {
                        L = l; R = r - 1;
                    }
                    L = max(L, l);
                    R = min(R, r - 1);
                }
                if (R < L) R = L;
                // L = l; R = r - 1;
                // L = max(l, L - 5);
                // R = min(r - 1, R + 5);
                int opt_val = 1e9;
                for (int m = L; m <= R; ++m) {
                    int cur = dp[l][m][2] + dp[m + 1][r][0];
                    if (opt_val > cur) {
                        opt_val = cur;
                        opt[l][r][3] = m;
                    }
                }
                dp[l][r][1] = min(dp[l][r][1], opt_val);
            }
            {
                int L = l;
                int R = r - 1;
                if (len > 2) {
                    L = opt[l][r - 1][4];
                    R = opt[l + 1][r][4];
                    if (L == -1 || R == -1) {
                        L = l; R = r - 1;
                    }
                    L = max(L, l);
                    R = min(R, r - 1);
                }
                if (R < L) R = L;
                // L = l; R = r - 1;
                //L = max(l, L - 10);
                //R = min(r - 1, R + 10);
                for (int m = L; m <= R; ++m) {
                    if (dp[l][r][2] > dp[l][m][2] + dp[m + 1][r][2]) {
                        dp[l][r][2] = dp[l][m][2] + dp[m + 1][r][2];
                        opt[l][r][4] = m;
                    }
                }
            }
            /*for (int m = l; m < r; ++m) {
                dp[l][r][0] = min(dp[l][r][0], dp[l][m][0] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][1] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][1]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][0]);
                dp[l][r][2] = min(dp[l][r][2], dp[l][m][2] + dp[m + 1][r][2]);
            }*/
            /*for (int m = r - 1; m < r; ++m) {
                dp[l][r][0] = min(dp[l][r][0], dp[l][m][0] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][1] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][1]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][0]);
                dp[l][r][2] = min(dp[l][r][2], dp[l][m][2] + dp[m + 1][r][2]);
            }*/
            if (s[l] == '>' || s[l] == '?') {
                for (int b = 0; b < 3; ++b) {
                    int cur = dp[l + 1][r][b] + (b == 0);
                    if (dp[l][r][0] > cur) {
                        dp[l][r][0] = cur;
                        //opt[l][r][0] = l;
                    }
                }
            }
            if (s[l] == '<' || s[l] == '?') {
                for (int b = 0; b < 3; ++b) {
                    int cur = dp[l + 1][r][b] + 1;
                    if (dp[l][r][max(1, b)] > cur) {
                        dp[l][r][max(1, b)] = cur;
                        //opt[l][r][max(1, b)] = l;
                    }
                }
            }
            if (s[r] == '<' || s[r] == '?') {
                for (int b = 0; b < 3; ++b) {
                    int cur = dp[l][r - 1][b] + (b == 2);
                    if (dp[l][r][2] > cur) {
                        dp[l][r][2] = cur;
                        //opt[l][r][2] = r - 1;
                    }
                }
            }
            if (s[r] == '>' || s[r] == '?') {
                for (int b = 0; b < 3; ++b) {
                    int cur = dp[l][r - 1][b] + 1;
                    if (dp[l][r][min(1, b)] > cur) {
                        dp[l][r][min(1, b)] = cur;
                        //opt[l][r][min(1, b)] = r - 1;
                    }
                }
            }
            //cerr << opt[l][r][2] << " ";
        }
        //cerr << "\n";
    }
    cout << n - *min_element(all(dp[0][n-1])) << '\n';
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed << setprecision(20);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    //cerr << "\n\nConsumed " << TIME << endl;
}
源文件, 语言: C++20

详细

Test #1:

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

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 322ms
memory: 3668kb

input:

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

output:

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

wrong answer 12th numbers differ - expected: '6', found: '5'
English 繁體中文 简体中文

服务器时间: 2024-12-12 04:28:55 | 开源项目