QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #445008 | #8521. Pattern Search II | ucup-team3792# | WA | 2ms | 9092kb | C++14 | 1.1kb | 2024-06-15 22:59:57 | 2024-06-15 22:59:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,f[150005][3][3];
char s[150005];
string g[3]={"","ba","baa"};
int main()
{
cin>>s+1;
n=strlen(s+1);
memset(f,0x3f,sizeof(f));
f[0][0][0]=0;
for(int i=0;i<n;i++)
{
for(int st1=0;st1<=2;st1++)
{
for(int st2=0;st2<=2;st2++)
{
// if(f[i][st1][st2]<1e9) cerr<<i<<" "<<st1<<" "<<st2<<" "<<f[i][st1][st2]<<"\n";
for(int j=1;j<=2;j++)
{
if(st1==st2&&st2==j) continue ;
string st=g[j];
do{
int k=i,t=0;
while(t<st.size()&&k<n&&s[k+1]==st[t]) t++,k++;
if(k!=i)
{
if(i==0&&k==n) f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+t);
else if(i==0) f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+(int)st.size());
else if(k==n) f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+t+(int)(g[j].size()-st.size()));
else f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+(int)g[j].length());
}
st.erase(st.begin());
}while(!st.empty());
}
}
}
}
int res=1e9;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
res=min(res,f[n][i][j]);
}
}
cout<<res;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8868kb
input:
aabbaab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8864kb
input:
a
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 9032kb
input:
b
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 8872kb
input:
aa
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 2ms
memory: 9056kb
input:
bb
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 2ms
memory: 9092kb
input:
ab
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 0ms
memory: 8864kb
input:
ba
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 8872kb
input:
bbba
output:
6
result:
wrong answer 1st numbers differ - expected: '7', found: '6'