#include <bits/stdc++.h> using namespace std; typedef long long ll; #define placementlelo vector<int> #define all(a) (a).begin() , (a).end() #define sz(a) ((int)((a).size())) const ll INF = 4e18; vector<placementlelo> dp(1e4+1 , placementlelo(1e4+1 , -1)); int f(int i , int j , int s , int r , string &x , string &y , string &y1) { if(i>j)return 0; if(dp[i][j] != -1)return dp[i][j]; int mini = 1e9; for(int k=i; k<=j; k++) { if(y1.find(x.substr(i , k-i+1)) != string::npos)mini = min(mini , r+f(k+1 , j , s , r , x , y , y1)); if(y.find(x.substr(i , k-i+1)) != string::npos)mini = min(mini , s+f(k+1 , j , s , r , x , y , y1)); } return mini; } int solve(int s , int r , string x, string y) { string y1 = y; reverse(all(y1)); return f(0 , sz(x)-1 , s, r , x , y , y1); } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); string x , y; cin >> x >> y; int s, r; cin >> s >> r; int ans = solve(s , r, x , y); cout << ans; return 0; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter