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