SPOJ MC — Minimum Cost

Problem Name: MC — Minimum Cost

This article is contributed by Rainy Jain

Problem Statement :

Given two string S and T. you can delete a character from S with cost 15 and a Character T with cost 30. Your goal is to make the string equal (same). It is not mandatory to delete character .

For example : S = a5b and T = 2ab . Now , if we delete X from S and Y from T, then total cost = 15+30 = 45. And S and T will become ab.

Another example : S = ab , T = cd , Now total cost = 15 + 15 + 30 + 30 = 90.

Another example : S = abcd , T = acdb , Now total cost = 15 + 30 = 45.

Input:

Input consists of pairs of lines. The first line of a pair contains the first string S and the second line contains the second string T. Each string is on a separate line and consists of at most 1,000 characters . The end of input occurs when the first sequence starts with an “#”character (without the quotes).

Output:

For each subsequent pair of input lines, output a line containing one integer number which the minimum cost to make the string equal (same).

Solution:

Difficulty:Easy Dp

This problem is a variant of Edit Distance Problem(https://en.wikipedia.org/wiki/Edit_distance)

The only difference is the replace and insert operations are not allowed.So the problem boils down to Longest Common Subsequence Problem (https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
The idea is that except common subsequence we have to delete all other characters from both strings and calculate respective costs.

CODE C++

#include <iostream>
#include <string>
using namespace std;
// function to calculate length of longest common subsequence
int lcs(string s,int l1,string t,int l2)
{
int a[1001][1001];
for(int i=0;i<=l1;i++)
{
for(int j=0;j<=l2;j++)
{
if(i==0||j==0)
a[i][j]=0;
else if(s[i-1]!=t[j-1])
a[i][j]=max(a[i-1][j],a[i][j-1]);
else
a[i][j]=a[i-1][j-1]+1;
}
}
return a[l1][l2];
}
int main()
{
while(1)
{
string s,t;
cin>>s>>t;
if(s[0]=='#')
break;
int l1=s.length();
int l2=t.length();
int n=lcs(s,l1,t,l2);
//calculation of cost
cout<<15*(l1-n)+30*(l2-n)<<endl;
}
return 0;
}