UVa:10192 Vacation

순수한 LCS입니다.
 
제목의 뜻을 잘못 이해했다. 중복된 도시가 통계를 내지 않는 줄 알고 판정 결과 WA에 4번 가입했다.
 
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
string str1,str2;
int dp[105][105];
int main()
{
    int kase=0;
    while(getline(cin,str1)&&str1[0]!='#')
    {
        memset(dp,0,sizeof(dp));
        getline(cin,str2);
        str1=' '+str1;
        str2=' '+str2;
        for(int i=1; i<str1.size(); ++i)

            for(int j=1; j<str2.size(); ++j)
                if(str1[i]==str2[j])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        cout<<"Case #"<<++kase<<": you can visit at most "<<dp[str1.size()-1][str2.size()-1]<<" cities."<<endl;
    }
    return 0;
}