台中女中程式解題系統:b033: 兩隻猴子

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b033
此題用 Dynamic Programming ,可參考 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS  。

演算法(底下文字是從https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS 節錄出來)
function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

程式碼:
  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <vector>  
  4.   
  5. using namespace std;  
  6.   
  7. int lengthOfLCS(string x, int m, string y, int n) {  
  8.     int C[m+1][n+1];  
  9.   
  10.     for(int i = 0; i <= m; i++)  
  11.     {  
  12.         for(int j = 0; j <= n; j++)  
  13.         {  
  14.             if(i == 0 || j == 0)  
  15.                 C[i][j] = 0;  
  16.             else if(x[i-1] == y[j-1])  
  17.                 C[i][j] = C[i-1][j-1] + 1;  
  18.             else  
  19.                 C[i][j] = max(C[i][j-1], C[i-1][j]);  
  20.         }  
  21.     }  
  22.   
  23.     return C[m][n];  
  24. }  
  25.   
  26. int main()  
  27. {  
  28.     string a, b;  
  29.     cin >> a >> b;  
  30.   
  31.     cout << lengthOfLCS(a, a.length(), b, b.length());  
  32.     return 0;  

沒有留言: