UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212115#3817. 写字xxc501ms1300kbC++928b2024-10-13 11:19:382024-10-13 12:24:09

answer

#include<iostream>
#include<cmath>
using namespace std;
const int MAX=0x7fffffff;
int v[500][305];
int lens,lent,ans=MAX,finished;
string s,t;
void f(int l,int k,int sum,bool flag)
{
//	cout<<l<<' '<<k<<' '<<sum<<endl;
	if(finished) return;
	if(k==lent-1&&t[k]==s[l])
	{
		ans=min(ans,sum);
		if(ans==lent-1)
		{
			finished=1;
		}
		return;
	}
	if(l!=0)
	{
		if(s[l-1]==t[k+1])
		{
			f(l-1,k+1,sum+1,0);
		}
	}
	if(l!=lens-1)
	{
		if(s[l+1]==t[k+1])
		{
			f(l+1,k+1,sum+1,0);
		}
	}
	if(flag==0)
	{
		for(int i=1;i<=v[s[l]][0];i++)
		{
			if(v[s[l]][i]==l) continue;
			f(v[s[l]][i],k,sum+abs(v[s[l]][i]-l),1);
		}
	}
}
int main()
{
	cin>>lens>>lent;
	cin>>s>>t;
	for(int i=0;i<lens;i++)
	{
		v[s[i]][++v[s[i]][0]]=i;
	}
	for(int i=1;i<=v[t[0]][0];i++)
	{
		f(v[t[0]][i],0,0,0);
	}
	if(ans==MAX)
	{
		cout<<-1<<endl;
	}else
	{
		cout<<ans<<endl;
	}
	return 0;
} 

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1244kb

input:

1 1
v
v

output:

0

result:

ok 1 number(s): "0"

Test #2:

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

input:

5 5
bacbb
cabcb

output:

7

result:

ok 1 number(s): "7"

Subtask #2:

score: 30
Accepted

Test #3:

score: 30
Accepted
time: 0ms
memory: 1300kb

input:

26 300
ywzhvjnpdfqtukimsrbxageloc
brsmsrbxbxbxbxagagagegelococololegaxagaxaxbxbrbxbrsrsmikimikikimim...

output:

299

result:

ok 1 number(s): "299"

Test #4:

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

input:

26 300
wempkfsunqgytdzibajorvxhlc
gqnununqnusfsununununqnununususunusususfkpmewewewewewempkfkpkpmpmp...

output:

299

result:

ok 1 number(s): "299"

Test #5:

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

input:

26 300
gieywcraxnvblsuojfpthdkmzq
nvbvbvblsusuojfjojouoususlslbvnxnxnxarcraxnvnvnxnxnvnxnxnvblslsusu...

output:

299

result:

ok 1 number(s): "299"

Subtask #3:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

300 300
hgbfdbgcghedefchdabhgdddahcdedebceffegfbceehceeheggffhhddbecbfdhceeedcaeeebdaddfgccggfdcachg...

output:


result: