[HAOI2008]玩具取名

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

C++(clang++ 11.0.1) 解法, 执行用时: 192ms, 内存消耗: 1120K, 提交时间: 2023-04-28 22:51:02

#include<bits/stdc++.h>
using namespace std;
string wing = "WING";

string s;
vector<vector<pair<int, int>>> A(4);
int cache[4][211][211];
bool gao(int x, int l, int r) {
  if (l + 1 == r)  return wing[x] == s[l];
  auto &res = cache[x][l][r];
  if (res != -1) return res;
  res = 0;
  for (int i = l+1; i < r; i++) {
    for (auto &[a, b]: A[x]) if (gao(a, l, i) && gao(b, i, r))  return res = 1;
  }
  return res;
}
int main(){
  memset(cache, -1, sizeof(cache));
  vector<int> cnt(4); for (auto &x: cnt) cin >> x;
  for (int i = 0; i < 4; i++) {
    while (cnt[i]--) {
      char a, b; cin >> a >> b;
      A[i].push_back({wing.find(a), wing.find(b)});
    }
  }
  cin >> s;
  
  string ans;
  for (int i = 0; i < 4; i++) {
    if (gao(i, 0, s.size())) ans.push_back(wing[i]);
  }
  if (ans == "") ans = "The name is wrong!";
  cout << ans << endl;
}

详情