2012年9月5日

UVa 10066 - The Twin Towers


#include <cstdio>

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

int main() {
  int m, n, c = 1;
  while (scanf("%d%d", &m, &n) && m || n) {
    int i, j, a[101], b[101], dp[101][101] = {0};
    for (i = 1; i <= m; i++)
      scanf("%d", &a[i]);
    for (i = 1; i <= n; i++)
      scanf("%d", &b[i]);
    for (i = 1; i <= m; i++)
      for (j = 1; j <= n; j++)
        if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", c++, dp[m][n]);
  }
  return 0;
}

沒有留言:

張貼留言