UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212079#3817. 写字qinys10075ms1856kbC++1.3kb2024-10-13 11:01:032024-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