QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444913#8521. Pattern Search IIucup-team3792#WA 2ms8896kbC++141.0kb2024-06-15 22:16:412024-06-15 22:16:41

Judging History

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

  • [2024-06-15 22:16:41]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8896kb
  • [2024-06-15 22:16:41]
  • 提交

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) f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+t);
							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: 8896kb

input:

aabbaab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 2ms
memory: 8804kb

input:

a

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 8868kb

input:

b

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 8860kb

input:

aa

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

bb

output:

2

result:

wrong answer 1st numbers differ - expected: '3', found: '2'