QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#445082#8521. Pattern Search IIucup-team3608#WA 0ms3860kbC++232.0kb2024-06-15 23:23:532024-06-15 23:23:53

Judging History

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

  • [2024-06-15 23:23:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3860kb
  • [2024-06-15 23:23:53]
  • 提交

answer

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = long long;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
using namespace std;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    string s;
    cin>>s;
    int n = (int)s.size();
    if(n <= 2){
        if(s == "bb") cout<<"3\n";
        else cout<<n<<"\n";
        return 0;
    }
    // pos, # aab, # ab, # a
    vector dp(n+1, vector(4, vector(4, vector(3, inf))));
    vector<queue<array<int, 3>>>v(n + 1);
    if(s[0] == 'a'){
        dp[0][0][0][0] = 1;
        v[0].push({0, 0, 0});
        dp[1][0][0][1] = 1;
        v[1].push({0, 0, 1});
    }
    else{
        dp[0][0][1][1] = 1;
        v[0].push({0, 1, 1});
        dp[1][0][1][0] = 1;
        v[1].push({0, 1, 0});
    }
    for(int i=0;i<n;i++){
        while(!v[i].empty()){
            auto [j, k, l] = v[i].front();
            v[i].pop();
            if(j == 3 || k == 3) continue;
            if(l != 0){
                // can put b
                int ni = i + (s[i] == 'b');
                int nj = (l == 1) ? 0 : j + 1;
                int nk = (l == 2) ? 0 : k + 1;
                int nl = 0;
                if(dp[ni][nj][nk][nl] == inf){
                    dp[ni][nj][nk][nl] = dp[i][j][k][l] + 1;
                    v[ni].push({nj, nk, nl});
                }
            }
            if(l != 2){
                // can put a
                int ni = i + (s[i] == 'a');
                int nj = j;
                int nk = (l == 1) ? 0 : k;
                int nl = l + 1;
                if(dp[ni][nj][nk][nl] == inf){
                    dp[ni][nj][nk][nl] = dp[i][j][k][l] + 1;
                    v[ni].push({nj, nk, nl});
                }
            }
        }
    }
    int ans = inf;
    for(int j=0;j<3;j++){
        for(int k=0;k<3;k++){
            for(int l=0;l<3;l++) ans = min(ans, dp[n][j][k][l]);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

aabbaab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

a

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

b

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

aa

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

bb

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

ab

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

ba

output:

2

result:

ok 1 number(s): "2"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

bbba

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

abbbbbbbab

output:

18

result:

wrong answer 1st numbers differ - expected: '20', found: '18'