Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <string>
#define oo 1000000000
using namespace std;

string a,b;
int m,n,f[10100][1010];

int main()
{
    cin >> a >> b;
    n=b.size();
    while (!a.empty() && a[a.size()-1]=='*') a.erase(a.size()-1,1);
    if (a.empty())
    {
        puts("0");
        return 0;
    }
    m=a.size(); a="-"+a; b="-"+b;
    for (int i=0;i<=n;i++)
        for (int j=1;j<=m;j++)
            f[i][j]=oo;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if (f[i][j]!=oo)
            {
                if (a[j+1]=='*') 
                {
                    f[i+1][j]=min(f[i+1][j],f[i][j]+b[i+1]-'a'+1);
                    f[i][j+1]=min(f[i][j+1],f[i][j]);
                }
                if (a[j+1]>='a' && a[j+1]<='z' && a[j+1]!=b[i+1]) continue;
                f[i+1][j+1]=min(f[i+1][j+1],f[i][j]+b[i+1]-'a'+1);
            }           
    int ans=oo;
    for (int i=0;i<=n;i++) ans=min(ans,f[i][m]);
    cout << (ans==oo?-1:ans) << endl;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 11111;

char s[N], t[N];
vector<string> p;
int m, n;

int dp[N];
int sumCost[N];

void solve(string t) {
    for (int i = 0; i <= m; ++i) {
        dp[i] = N;
        if (i + t.size() <= m) {
            bool match = true;
            for (int j = 0; j < t.size(); ++j) if (t[j] != '?' && s[i + j] != t[j]) {
                match = false;
                break;
            }
            if (match) dp[i] = dp[i + t.size()];
        }
    }
    for (int i = m - 2; i >= 0; --i)
        dp[i] = min(dp[i], dp[i + 1]);
}

string reformat(char s[]) {
    string ans;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '?')
            ans += "(.{1})";
        else if (s[i] == '*')
            ans += ".*";
        else
            ans += s[i];
    }
    return ans;
}

int main() {
    cin >> t >> s;
    m = strlen(s), n = strlen(t);
    p.push_back("");
    for (int i = 0; i < n; ++i) {
        if (t[i] == '*') {
            if (p.back().size()) p.push_back("");
        } else {
            p.back() += t[i];
        }
    }
    while (!p.empty() && !p.back().size()) p.pop_back();
    for (int i = 0; i <= m; ++i) dp[i] = i;
    for (int j = (int)p.size() - 1; j >= 0; --j)
        solve(p[j]);
    int ans = N * 26;
    for (int i = m - 1; i >= 0; --i) sumCost[i] = sumCost[i + 1] + (s[i] - 'a' + 1);
    for (int i = 0; i < m; ++i) if (dp[i] != N) ans = min(ans, sumCost[i] - sumCost[dp[i]]);
    cout << (ans < N * 26 ? ans : -1) << endl;
    if (ans < N * 26) {
        string st;
        for (int i = 0; i < m; ++i) if (dp[i] != N && ans == sumCost[i] - sumCost[dp[i]]) {
            for (int j = i; j < dp[i]; ++j) cerr << s[j], st += s[j];
            cerr << endl;
            break;
        }
        //assert(regex_match(st, regex(reformat(t))));
    }
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

string s, t;
int f[1011][10111];

int main() {
    ios :: sync_with_stdio(false);
    while (cin >> t >> s) {
        int lt = t.length(), ls = s.length();

        REP(i,lt+1) REP(j,ls+3) {
            if (i == lt) f[i][j] = 0;
            else f[i][j] = 1000111;
        }
        int res = 1000111;
        FORD(i,lt-1,0) FORD(j,ls,0) {
            if (t[i] >= 'a' && t[i] <= 'z') {
                if (s[j] == t[i]) {
                    f[i][j] = f[i+1][j+1] + t[i] - 'a' + 1;
                }
            }
            else if (t[i] == '?') {
                if (j <= ls-1) f[i][j] = f[i+1][j+1] + s[j] - 'a' + 1;
            }
            else {
                if (j <= ls-1) {
                    f[i][j] = min(f[i+1][j], f[i][j+1] + s[j] - 'a' + 1);
                    f[i][j] = min(f[i][j], f[i+1][j+1] + s[j] - 'a' + 1);
                }
                else f[i][j] = f[i+1][j];
            }
            if (i == 0) res = min(res, f[i][j]);
        }
        if (res > 1000000) res = -1;
        cout << res << endl;
        break;
    }
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 10111
#define oo 1111111111
#define mod 10000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#include <conio.h>
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

string s,t,S[1010];
int m[maxn],f[1010][maxn],n,l;

bool check(int i,int vitri){
    if(S[i].length() + vitri > s.length()){
        return false;
    }
    for(int j = 0; j <S[i].length(); j++){
        if(S[i][j] != '?' && S[i][j] != s[vitri + j])
            return false;
    }
    return true;
}


int main(){

    //freopen("I.in","r",stdin);
    //freopen("O.out","w",stdout);

    cin >> t >> s;
    n = s.length();

    for(int i = 1; i <= n; i++){
        m[i] = m[i - 1] + s[i - 1] - 'a' + 1;
    }

    l = 0;
    for(int i = 0; i < t.length(); i++){
        if((i == 0 && t[i] != '*') || (t[i - 1] == '*' && t[i] != '*')){
            l++;
        }
        if(t[i] != '*') S[l].push_back(t[i]);
    }

    for(int i = 1; i <= l; i++){
        f[i][n+1] = f[i][n] = n;
        for(int j = n-1; j >= 0; j--){
            f[i][j] = f[i][j+1];
            if(check(i,j)){
                f[i][j] = j;
            }
        }
    }

    int kq = oo;
    for(int i = 0; i < n; i++){
        int run = i;
        for(int j = 1; j <= l; j++){
            if(run > n){
                break;
            }
            run = f[j][run] + S[j].length();
        }
       // printf("%d %d\n",i,run);
        if(run <= n) kq = min(kq, m[run] - m[i]);
    }

    if(kq < oo) printf("%d",kq);
    else printf("-1");

    return 0;
}