10192-Vacation-solution hints

https://uva.onlinejudge.org/external/101/10192.pdf

In first view you may think that it is hard one but not like that it's easy and if you know the LCS(Longest Common subsequence) then you can easily solve the problem . it's nothing but to find the common subsequence between two strings . For details of LCS algorithm please visit the links below : 

https://www.youtube.com/watch?v=NnD96abizww

http://www.thecrazyprogrammer.com/2015/05/c-program-for-longest-common-subsequence-problem.html

N.B : please be careful for using array because it may become the main  reason of getting Runtime error . 

An accepted code is given below : 

#include<bits/stdc++.h>

using namespace std;

int c[501][501];

int max1(int x , int y)

{

    if(x>y)

    {

        return x;

    }

    else

    {

        return y;

    }

}

int lcs(string x , string y)

{

    int m,n;

    m=x.length();

    n=y.length();

    for(int i=0;i<=x.length();i++)

    {

        c[i][0]=0;

    }

    for(int j=0;j<=y.length();j++)

    {

        c[0][j]=0;

    }

    for(int i=1;i<=x.length();i++)

    {

        for(int j=1;j<=y.length();j++)

        {

            if(x[i-1]==y[j-1])

            {

                c[i][j]=c[i-1][j-1]+1;

            }

            else

            {

                c[i][j]=max1(c[i-1][j],c[i][j-1]);

            }

        }

    }

    return c[m][n];

}

int main()

{

    string x,y;

    int i=1;

    while(getline(cin,x) && x!="#")

    {

        getline(cin,y);

    cout<<"Case #"<<i<<": you can visit at most "<<lcs(x,y)<<" cities."<<endl;

    i++;

    }

    return 0;

}

(Happy coding)