UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212181#3817. 写字zhangry00ms1272kbC++111.5kb2024-10-13 11:53:272024-10-13 12:30:28

answer

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define awa return 0;
using namespace std;
int n,m;
string s,t;
bool find(string s,string t)
{
    unordered_map<char,int>scnt;
    for(char c:s)
    {
        scnt[c]++;
    }
    unordered_map<char,int>tcnt;
    for(char c:t)
    {
        tcnt[c]++;
        if(scnt[c]<tcnt[c])
        {
            return false;
        }
    }
    return true;
}
signed main()
{
    IOS;
    unordered_map<char,vector<int>> pos;
    cin>>n>>m;
    cin>>s>>t;
    if(find(s,t))
    {
        for (int i = 0; i < n; ++i)
        {
            pos[s[i]].push_back(i);
        }
        vector<int> dp(m+1,numeric_limits<int>::max());
        dp[0]=0;
        for (int i=0;i<m;++i)
        {
            char c=t[i];
            if (pos.find(c)==pos.end())
            {
                cout<<-1<<endl;
                return 0;
            }
            for (int j=0;j<pos[c].size(); ++j) {
                int s_idx=pos[c][j];
                for (int k=0;k<=i;++k)
                {
                    if(dp[k]!=numeric_limits<int>::max())
                    {
                        int t=(k==0)?s_idx+1:dp[k]+abs(s_idx-pos[s[k-1]].back())+1;
                        dp[i+1]=min(dp[i+1],t);
                    }
                }
            }
        }
        cout<<dp[m]<<endl;
    }
    else
    {
        cout<<-1;
        awa
    }
    awa
}
//

Details

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1260kb

input:

1 1
v
v

output:

1

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 1268kb

input:

26 300
ywzhvjnpdfqtukimsrbxageloc
brsmsrbxbxbxbxagagagegelococololegaxagaxaxbxbrbxbrsrsmikimikikimim...

output:

-1

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 1272kb

input:

300 300
hgbfdbgcghedefchdabhgdddahcdedebceffegfbceehceeheggffhhddbecbfdhceeedcaeeebdaddfgccggfdcachg...

output:

-1

result:

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