QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#444880#8521. Pattern Search IIucup-team3792#WA 2ms9104kbC++141.2kb2024-06-15 21:56:292024-06-15 21:56:29

Judging History

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

  • [2024-06-15 21:56:29]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9104kb
  • [2024-06-15 21:56:29]
  • 提交

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++)
			{
				for(int j=1;j<=2;j++)
				{
					if(st1==st2&&st2==j) continue ;
					string st=g[j];
					if(i==0)
					{
						do{
							int k=i,t=0;
							while(t<st.size()&&k<n&&s[k+1]==st[t]) t++,k++;
							if(k!=i)
							{
								if(k!=n) f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+(int)st.length());
								else f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+t);
							}
							st.erase(st.begin());
						}while(!st.empty());
					}
					else
					{
						int k=i,t=0;
						while(t<st.size()&&k<n&&s[k+1]==st[t]) t++,k++;
						if(k!=i)
						{
							if(k!=n) f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+(int)st.length());
							else f[k][st2][j]=min(f[k][st2][j],f[i][st1][st2]+t);
						}						
					}
				}
			}
		}
	}
	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;
}

詳細信息

Test #1:

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

input:

aabbaab

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

a

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

b

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

aa

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

bb

output:

3

result:

ok 1 number(s): "3"

Test #6:

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

input:

ab

output:

2

result:

ok 1 number(s): "2"

Test #7:

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

input:

ba

output:

2

result:

ok 1 number(s): "2"

Test #8:

score: -100
Wrong Answer
time: 2ms
memory: 9104kb

input:

bbba

output:

6

result:

wrong answer 1st numbers differ - expected: '7', found: '6'