UVA 10192 - Vacation(cpp file)

Problem Type : String DP(LCS)




#include<stdio.h>
#include<string.h>
int arr[1003][1003];
int main()
{
    char ch[10000],des[10000];
    int len1,len2,i,j,k,p,q,cou=0;
    while(gets(ch))
    {
        cou++;
        if(strcmp(ch,"#")==0)
            break;
        gets(des);
        memset(arr,0,sizeof(arr));
        len1= strlen(ch);
        len2= strlen(des);
        for(i=len1; i>0; i--)
        {
            ch[i]=ch[i-1];
        }
        len1++;
        ch[len1] = '\0';
       // printf("%s\n",ch);
        for(i=len2; i>0; i--)
        {
            des[i]=des[i-1];
        }
        len2++;
        des[len2] = '\0';
        //printf("%s\n",des);
        for(i=1; i<len1; i++)
        {
            for(j=1; j<len2; j++)
            {
                if(ch[i]==des[j])
                {
                    arr[i][j]=arr[i-1][j-1]+1;
                }
                else
                {
                    p=arr[i-1][j];
                    q=arr[i][j-1];
                    if(p>q)
                    {
                        arr[i][j]=p;
                    }
                    else
                    {
                        arr[i][j]=q;
                    }
                }
            }
        }

        printf("Case #%d: you can visit at most %d cities.\n",cou,arr[len1-1][len2-1]);
        memset(ch,'\0',sizeof(ch));
        memset(des,'\0',sizeof(des));
    }


}