Saleh127

UVA 164 / DP - Edit dis

Dec 1st, 2021
558
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-29-17.34.32
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define get_lost_idiot return 0
  9. #define nl '\n'
  10.  
  11. string a,b;
  12.  
  13. ll dp[30][30],n,m;
  14.  
  15. ll cost(ll i,ll j)
  16. {
  17.     if(i==n) return m-j;
  18.     if(j==m) return n-i;
  19.  
  20.     if(dp[i][j]!=-1) return dp[i][j];
  21.  
  22.     ll ans;
  23.  
  24.     if(a[i]==b[j])
  25.     {
  26.          ans=cost(i+1,j+1);
  27.     }
  28.     else
  29.     {
  30.          ll o=1+cost(i+1,j+1);
  31.          ll p=1+cost(i+1,j);
  32.          ll q=1+cost(i,j+1);
  33.  
  34.          ans=min({o,p,q});
  35.     }
  36.  
  37.     return dp[i][j]=ans;
  38. }
  39.  
  40.  
  41.  
  42. void way(ll i,ll j)
  43. {
  44.      if(i==n)
  45.      {
  46.           while(j<m)
  47.           {
  48.                cout<<"I"<<b[j];
  49.                if(j<9) cout<<"0";
  50.                cout<<j+1;
  51.                j++;
  52.           }
  53.           return ;
  54.      }
  55.      if(j==m)
  56.      {
  57.           while(i<n)
  58.           {
  59.                cout<<"D"<<a[i];
  60.                if(j<9) cout<<"0";
  61.                cout<<j+1;
  62.                i++;
  63.           }
  64.           return ;
  65.      }
  66.  
  67.      if(a[i]==b[j]) way(i+1,j+1);
  68.  
  69.      else
  70.      {
  71.           if(dp[i][j]==dp[i+1][j]+1)
  72.           {
  73.                cout<<"D"<<a[i];
  74.                if(j<9) cout<<"0";
  75.                cout<<j+1;
  76.  
  77.                way(i+1,j);
  78.           }
  79.           else if(dp[i][j]==dp[i][j+1]+1)
  80.           {
  81.                cout<<"I"<<b[j];
  82.                if(j<9) cout<<"0";
  83.                cout<<j+1;
  84.  
  85.                way(i,j+1);
  86.           }
  87.           else
  88.           {
  89.                cout<<"C"<<b[j];
  90.                if(j<9) cout<<"0";
  91.                cout<<j+1;
  92.  
  93.                way(i+1,j+1);
  94.           }
  95.      }
  96.      return;
  97. }
  98.  
  99.  
  100. int main()
  101. {
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0);
  104.     cout.tie(0);
  105.  
  106.      while(cin>>a)
  107.      {
  108.           if(a=="#") break;
  109.           cin>>b;
  110.  
  111.           n=a.size();
  112.           m=b.size();
  113.  
  114.           memset(dp,-1,sizeof dp);
  115.  
  116.           ll w=cost(0,0);
  117.  
  118.           way(0,0);
  119.  
  120.           cout<<"E"<<nl;
  121.      }
  122.  
  123. }
  124.  
RAW Paste Data