Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <vector>
- using namespace std;
- int n;
- pair<string, vector<int> > v[10005];
- vector<pair<pair<string, int>, vector<int> > > g[1005];
- int dp[10005];
- int backtrack[10005];
- int f(int at)
- {
- if(dp[at] != -1) {
- return dp[at];
- }
- int result = 0;
- int sz = (int) v[at].first.size();
- int max_result = 0;
- for(int i = 0; i < (int) g[sz + 1].size(); i++) {
- string tmp = g[sz + 1][i].first.first;
- vector<int> cnt1 = v[at].second;
- vector<int> cnt2 = g[sz + 1][i].second;
- bool flag = false, ok = true;
- for(int j = 0; j < 26; j++) {
- if(abs(cnt1[j] - cnt2[j]) == 1 and !flag) {
- flag = true;
- continue;
- }
- if(abs(cnt1[j] - cnt2[j]) > 0) {
- ok = false;
- break;
- }
- }
- if(ok) {
- result = f(g[sz + 1][i].first.second) + 1;
- if(result > max_result) {
- max_result = result;
- backtrack[at] = g[sz + 1][i].first.second;
- }
- }
- }
- return dp[at] = max_result;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- memset(dp, -1, sizeof dp);
- memset(backtrack, -1, sizeof backtrack);
- cin>>n;
- for(int i = 0; i < n; i++) {
- cin >>v[i].first;
- vector<int> cnt(26, 0);
- for(int j = 0; j < (int) v[i].first.size(); j++) {
- cnt[v[i].first[j] - 'A']++;
- }
- v[i].second = cnt;
- g[(int)v[i].first.size()].emplace_back(make_pair(make_pair(v[i].first, i), cnt));
- }
- int result = 0, idx = 0;
- for(int i = 0; i < n; i++) {
- if((int) v[i].first.size() <= 2 and f(i) + 1 > result) {
- result = f(i) + 1;
- idx = i;
- }
- }
- if(result <= 1) {
- cout << 1 << endl;
- cout << "A" << endl;
- return 0;
- }
- vector<string> answer;
- answer.push_back(string() + v[idx].first[0]);
- if(v[idx].first.size() != 1) {
- answer.push_back(v[idx].first);
- }
- idx = backtrack[idx];
- while(idx != -1) {
- answer.push_back(v[idx].first);
- idx = backtrack[idx];
- }
- cout << answer.size() << endl;
- for(int i =0 ; i < (int) answer.size(); i++) {
- cout << answer[i] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement