Here is the problem statement
http://www.spoj.com/problems/MC/
The costs of removing element sometimes confuses the solver. What if I told you that the cost is not changing making it difficult? Its just a number made up by the task creator. Note that for making them equal we need to delete some amount of chars from both of them or from one of them but the point is that there is only one way of doing that. We need to calculate the LCS longest common subsequence of both of them . The counted LCS is the string which is going to remain after we remove some chas from both of the, The answer will be (If we consider the length of LCS L) ANS=(s1.size()-L)*15+(s2.size()-L)*30; If you need more information about LCS go here.
http://www.spoj.com/problems/MC/
The costs of removing element sometimes confuses the solver. What if I told you that the cost is not changing making it difficult? Its just a number made up by the task creator. Note that for making them equal we need to delete some amount of chars from both of them or from one of them but the point is that there is only one way of doing that. We need to calculate the LCS longest common subsequence of both of them . The counted LCS is the string which is going to remain after we remove some chas from both of the, The answer will be (If we consider the length of LCS L) ANS=(s1.size()-L)*15+(s2.size()-L)*30; If you need more information about LCS go here.
dp giving tle....any other way for this?
ReplyDelete