ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212079 | #3817. 写字 | qinys | 100 | 75ms | 1856kb | C++ | 1.3kb | 2024-10-13 11:01:03 | 2024-10-13 12:20:37 |
answer
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > q;
int dis[310][310]={},pos[26][310]={},tmp,u,w,n,m,t;
string s,s1;
int main(){
cin>>n>>m>>s>>s1;
for(int i=0;i<n;i++){
u=s[i]-'a';
pos[u][++pos[u][0]]=i;
}
u=s1[0]-'a';
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=pos[u][0];i++){
dis[1][pos[u][i]]=0;
q.push(make_pair(0,make_pair(1,pos[u][i])));
}
while(!q.empty()){
w=q.top().second.first;
u=q.top().second.second;
t=q.top().first;
q.pop();
if(dis[w][u]!=t) continue;
if(w==m){
cout<<t;
return 0;
}
for(int i=-1;i<2;i+=2){
if(u+i<0||u+i>=n||s[u+i]!=s1[w]) continue;
if(t+1<dis[w+1][u+i]){
dis[w+1][u+i]=t+1;
q.push(make_pair(t+1,make_pair(w+1,u+i)));
}
}
for(int i=1;i<=pos[s[u]-'a'][0];i++){
tmp=pos[s[u]-'a'][i];
if(tmp==u) continue;
if(t+abs(u-tmp)<dis[w][tmp]){
dis[w][tmp]=t+abs(u-tmp);
q.push(make_pair(dis[w][tmp],make_pair(w,tmp)));
}
}
}
cout<<-1;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1624kb
input:
1 1 v v
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1620kb
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: 1652kb
input:
26 300 ywzhvjnpdfqtukimsrbxageloc brsmsrbxbxbxbxagagagegelococololegaxagaxaxbxbrbxbrsrsmikimikikimim...
output:
299
result:
ok 1 number(s): "299"
Test #4:
score: 0
Accepted
time: 1ms
memory: 1652kb
input:
26 300 wempkfsunqgytdzibajorvxhlc gqnununqnusfsununununqnununususunusususfkpmewewewewewempkfkpkpmpmp...
output:
299
result:
ok 1 number(s): "299"
Test #5:
score: 0
Accepted
time: 0ms
memory: 1652kb
input:
26 300 gieywcraxnvblsuojfpthdkmzq nvbvbvblsusuojfjojouoususlslbvnxnxnxarcraxnvnvnxnxnvnxnxnvblslsusu...
output:
299
result:
ok 1 number(s): "299"
Subtask #3:
score: 50
Accepted
Test #6:
score: 50
Accepted
time: 9ms
memory: 1676kb
input:
300 300 hgbfdbgcghedefchdabhgdddahcdedebceffegfbceehceeheggffhhddbecbfdhceeedcaeeebdaddfgccggfdcachg...
output:
3643
result:
ok 1 number(s): "3643"
Test #7:
score: 0
Accepted
time: 6ms
memory: 1660kb
input:
300 300 gecffgfgddecebdgbhfccebecfddfgegfaedfehefhghahaecfbffdbbgahbecaabddefhhcgehbedfeegegddccgagb...
output:
4073
result:
ok 1 number(s): "4073"
Test #8:
score: 0
Accepted
time: 0ms
memory: 1676kb
input:
300 300 hbbhghebbgfcabfecgfcefafhddhfcaeedbfhhdhacaedbcbhgfhgbefabhgcddhecdfeagefeaceffffgdcacaacbee...
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 4ms
memory: 1660kb
input:
300 300 bdgebeggcabbbdbddgdehegbegfeghhgdcfadddghdcfbafhfedegffddfbcedgcacagaagfcbcggfbefheceagadeah...
output:
4002
result:
ok 1 number(s): "4002"
Test #10:
score: 0
Accepted
time: 55ms
memory: 1856kb
input:
300 300 bdcabacccabbbdbddcdadacbacbacddcdcbadddcddcbbabdbadacbbddbbcadccacacaacbcbcccbbabdacaacadaad...
output:
782
result:
ok 1 number(s): "782"
Extra Test:
score: 0
Extra Test Passed