hdu 1159

1、題目大意

我們稱序列Z=<z1,z2, ...,zk>是序列X=<x1,x2,...,xm>的子序列當且僅當存在嚴格上升的序列<i1,i2,...,ik>,使得對j=1,2,...,k, 有xij=zj。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。
現在給出兩個序列X和Y,你的任務是找到X和Y的最大公共子序列,也就是說要找到一個最長的序列 Z,使得Z既是X的子序列也是Y的子序列。

2、對最長公共子序列的感性認識

好,以字符串abcfbc 和 abfcab 為例

表格中的數字嘛.....姑且解釋為子串的最大公共子串的長度.最優子結構這個東西只能意會啊.

以圖中標記的數字為例,它代表 子串  abc 和 abfcab的最長公共子串.

3、代碼如下：

/*
 * 1159_1.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: 黃東東
 *      為了能有章澤天這樣的女朋友而不斷努力。。。
 *
 */ 
 
#include <stdio.h>  
#include <string.h>  
 
int dp[1005][1005]; 
 
int max(int a, int b) { 
    return (a > b) ? a : b; 
} 
 
int main() { 
 
    char stra[1001], strb[1001];//數組要開的足夠大，否則會出錯  
 
    int i, k; 
    while (scanf("%s%s", stra, strb) != EOF) { 
 
        int m = strlen(stra); 
        int n = strlen(strb); 
 
        memset(dp, 0, sizeof(dp)); 
 
        for (i = 1; i <= m; ++i) { 
            for (k = 1; k <= n; ++k) { 
                if (stra[i - 1] == strb[k - 1]) { 
                    dp[i][k] = dp[i - 1][k - 1] + 1; 
                } else { 
                    dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]); 
                } 
            } 
        } 
 
        printf("%d\n", dp[m][n]); 
    } 
    return 0; 
} 

/*
 * 1159_1.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: 黃東東
 *      為了能有章澤天這樣的女朋友而不斷努力。。。
 *
 */

#include <stdio.h>
#include <string.h>

int dp[1005][1005];

int max(int a, int b) {
 return (a > b) ? a : b;
}

int main() {

 char stra[1001], strb[1001];//數組要開的足夠大，否則會出錯

 int i, k;
 while (scanf("%s%s", stra, strb) != EOF) {

  int m = strlen(stra);
  int n = strlen(strb);

  memset(dp, 0, sizeof(dp));

  for (i = 1; i <= m; ++i) {
   for (k = 1; k <= n; ++k) {
    if (stra[i - 1] == strb[k - 1]) {
     dp[i][k] = dp[i - 1][k - 1] + 1;
    } else {
     dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]);
    }
   }
  }

  printf("%d\n", dp[m][n]);
 }
 return 0;
}

以下是c++實現。其實都差不多

/*
 * 1159_2.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: Administrator
 */ 
 
#include <iostream>  
 
using namespace std; 
 
int dp[1005][1005]; 
 
int max(int a , int b){ 
    return (a>b)?a:b; 
} 
int main() { 
 
    string stra, strb; 
 
    while (cin >> stra >> strb) { 
        int m = stra.length(); 
        int n = strb.length(); 
        for (int i = 1; i <= m; ++i) { 
            for (int k = 1; k <= n; ++k) { 
                if (stra[i - 1] == strb[k - 1]) { 
                    dp[i][k] = dp[i - 1][k - 1] + 1; 
                } else { 
                    dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]); 
                } 
            } 
        } 
 
 
        cout<<dp[m][n]<<endl; 
    } 
    return 0; 
} 

/*
 * 1159_2.cpp
 *
 *  Created on: 2013年7月31日
 *      Author: Administrator
 */

#include <iostream>

using namespace std;

int dp[1005][1005];

int max(int a , int b){
 return (a>b)?a:b;
}
int main() {

 string stra, strb;

 while (cin >> stra >> strb) {
  int m = stra.length();
  int n = strb.length();
  for (int i = 1; i <= m; ++i) {
   for (int k = 1; k <= n; ++k) {
    if (stra[i - 1] == strb[k - 1]) {
     dp[i][k] = dp[i - 1][k - 1] + 1;
    } else {
     dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]);
    }
   }
  }


  cout<<dp[m][n]<<endl;
 }
 return 0;
}