SPOJ MC - Minimum Cost

Problem Name: MC - Minimum Cost

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;
}