Advertisement
Saleh127

SPOJ ADASEQEN / DP

Nov 9th, 2021
655
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-09-16.22.11
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll dp[2005][2005];
  13.  
  14. int main()
  15. {
  16.    ios_base::sync_with_stdio(0);
  17.    cin.tie(0);cout.tie(0);
  18.  
  19.  
  20.    map<char,ll>x;
  21.  
  22.    string a,b;
  23.    ll n,m,i,j,k,l;
  24.  
  25.    cin>>n>>m;
  26.  
  27.    char c='a';
  28.  
  29.    for(i=0;i<26;i++)
  30.    {
  31.         cin>>j;
  32.  
  33.         x[c]=j;
  34.         c++;
  35.    }
  36.  
  37.    cin.ignore();
  38.  
  39.    cin>>a>>b;
  40.  
  41.  
  42.    for(i=1;i<=n;i++)
  43.    {
  44.         for(j=1;j<=m;j++)
  45.         {
  46.  
  47.              if(a[i-1]==b[j-1])
  48.              {
  49.                   dp[i][j]=max(dp[i][j],dp[i-1][j-1]+x[a[i-1]]);
  50.              }
  51.  
  52.              else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  53.         }
  54.    }
  55.  
  56.  
  57.    cout<<dp[n][m]<<nl;
  58.  
  59.  
  60.    get_lost_idiot;
  61. }
  62.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement