ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#212115 | #3817. 写字 | xxc | 50 | 1ms | 1300kb | C++ | 928b | 2024-10-13 11:19:38 | 2024-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...