寒武纪9.22笔试a满了

#include <iostream> (30316)#include <string> #include <vector> (30320)#include <set> #include <algorithm> using namespace std; int main() { string a, b; cin >> a >> b; //前向DP vector<vector<int>> dps(b.size() + 1, vector<int>(a.size() + 1, 0)); for (int i = 1; i <= b.size(); ++i) { for (int j = 1; j <= a.size(); ++j) { dps[i][j] = max(dps[i - 1][j], dps[i][j - 1]); if (b[i - 1] == a[j - 1]) { if (dps[i - 1][j - 1] + 1 > dps[i][j]) dps[i][j] = dps[i - 1][j - 1] + 1; } } } //后向DP vector<vector<int>> dps2(b.size() + 1, vector<int>(a.size() + 1, 0)); for (int i = 1; i <= b.size(); ++i) { for (int j = 1; j <= a.size(); ++j) { dps2[i][j] = max(dps2[i - 1][j], dps2[i][j - 1]); if (b[b.size() - i] == a[a.size() - j]) { if (dps2[i - 1][j - 1] + 1 > dps2[i][j]) dps2[i][j] = dps2[i - 1][j - 1] + 1; } } } int maxNums = dps[b.size()][a.size()] + 1; int res = 0; //补的位置 for (int i = 0; i <= a.size(); i++) { //该位置要能匹配一个b的字符,字符不重复 set<char> store; for (int j = 0; j < b.size(); j++) { if (store.find(b[j]) != store.end()) continue; int sum = dps[j][i] + dps2[b.size() - j - 1][a.size() - i] + 1; if (sum == maxNums) { store.insert(b[j]); res += 1; } } } cout << res; }