2013年3月28日

UVa 531 - Compromise


#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int prev[101][101], first;
vector<string> v1, v2;

void print(int i, int j) {
  if (prev[i][j] == 1) print(i - 1, j - 1);
  else if (prev[i][j] == 2) print(i - 1, j);
  else if (prev[i][j] == 3) print(i, j - 1);
  if (prev[i][j] == 1) printf("%s%s", first ? "" : " ", v1[i].c_str()), first = 0;
}
int main() {
  char voc[99];
  while (scanf("%s", voc) == 1) {
    v1.clear();
    v2.clear();
    v1.push_back("");
    v2.push_back("");
    do {
      v1.push_back(voc);
    } while (scanf("%s", voc) && voc[0] != '#');
    while (scanf("%s", voc) && voc[0] != '#') v2.push_back(voc);
    int dp[101][101] = {};
    memset(prev, 0, sizeof(prev));
    for (int i = 1; i < v1.size(); i++)
      for (int j = 1; j < v2.size(); j++)
        if (v1[i] == v2[j]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
          prev[i][j] = 1;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
          dp[i][j] = dp[i - 1][j];
          prev[i][j] = 2;
        } else {
          dp[i][j] = dp[i][j - 1];
          prev[i][j] = 3;
        }
    first = 1;
    print(v1.size() - 1, v2.size() - 1);
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言