Advertisement
Josif_tepe

Untitled

Oct 16th, 2022
1,047
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int n;
  7. pair<string, vector<int> > v[10005];
  8. vector<pair<pair<string, int>, vector<int> > > g[1005];
  9. int dp[10005];
  10. int backtrack[10005];
  11. int f(int at)
  12. {
  13.     if(dp[at] != -1) {
  14.         return dp[at];
  15.     }
  16.     int result = 0;
  17.     int sz = (int) v[at].first.size();
  18.     int max_result = 0;
  19.     for(int i = 0; i < (int) g[sz + 1].size(); i++) {
  20.         string tmp = g[sz + 1][i].first.first;
  21.         vector<int> cnt1 = v[at].second;
  22.         vector<int> cnt2 = g[sz + 1][i].second;
  23.         bool flag = false, ok = true;
  24.         for(int j = 0; j < 26; j++) {
  25.             if(abs(cnt1[j] - cnt2[j]) == 1 and !flag) {
  26.                 flag = true;
  27.                 continue;
  28.             }
  29.              if(abs(cnt1[j] - cnt2[j]) > 0) {
  30.                 ok = false;
  31.                 break;
  32.             }
  33.         }
  34.         if(ok) {
  35.             result = f(g[sz + 1][i].first.second) + 1;
  36.             if(result > max_result) {
  37.                 max_result = result;
  38.                 backtrack[at] = g[sz + 1][i].first.second;
  39.             }
  40.         }
  41.     }
  42.     return dp[at] = max_result;
  43. }
  44. int main()
  45. {
  46.     ios_base::sync_with_stdio(false);
  47.     memset(dp, -1, sizeof dp);
  48.     memset(backtrack, -1, sizeof backtrack);
  49.     cin>>n;
  50.     for(int i = 0; i < n; i++) {
  51.         cin >>v[i].first;
  52.  
  53.         vector<int> cnt(26, 0);
  54.        
  55.         for(int j = 0; j < (int) v[i].first.size(); j++) {
  56.             cnt[v[i].first[j] - 'A']++;
  57.         }
  58.         v[i].second = cnt;
  59.         g[(int)v[i].first.size()].emplace_back(make_pair(make_pair(v[i].first, i), cnt));
  60.      
  61.     }
  62.     int result = 0, idx = 0;
  63.     for(int i = 0; i < n; i++) {
  64.         if((int) v[i].first.size() <= 2 and f(i) + 1 > result) {
  65.             result = f(i) + 1;
  66.             idx = i;
  67.         }
  68.     }
  69.    
  70.     if(result <= 1) {
  71.         cout << 1 << endl;
  72.         cout << "A" << endl;
  73.         return 0;
  74.     }
  75.     vector<string> answer;
  76.     answer.push_back(string() + v[idx].first[0]);
  77.     if(v[idx].first.size() != 1) {
  78.         answer.push_back(v[idx].first);
  79.     }
  80.     idx = backtrack[idx];
  81.     while(idx != -1) {
  82.         answer.push_back(v[idx].first);
  83.         idx = backtrack[idx];
  84.     }
  85.    
  86.     cout << answer.size() << endl;
  87.     for(int i =0 ; i < (int) answer.size(); i++) {
  88.         cout << answer[i] << "\n";
  89.     }
  90.     return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement