UVa 10192 Vacation

解題：標準LCS

 1  #include <stdio.h>

 2  #include <iostream>

 3  #include <algorithm>

 4  #include <string>

 5  #include <vector>

 6  using namespace std;

 7  int main()

 8  {

 9      string str1,str2;

10      int cas=1;

11      while(getline(cin,str1) && str1!="#")

12      {

13          getline(cin,str2);

14          vector < vector<int> > lcs(105,vector<int> (105,0));

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

16          {

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

18              {

19                  if(str1[i-1]==str2[j-1])

20                      lcs[i][j]=lcs[i-1][j-1]+1;

21                  else

22                      lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);

23              }

24          }

25          printf("Case #%d: you can visit at most %d cities.\n",cas++,lcs[str1.length()][str2.length()]);

26      }

27 

28 

29 

30      return 0;

31  }