Advertisement
Josif_tepe

Untitled

Sep 26th, 2022
908
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <cstring>
  7. #include <set>
  8. //#include <bits/stdc++.h>
  9. using namespace std;
  10. vector<string>s;
  11. int n;
  12.  
  13. vector<pair<string, int> > words[1005];
  14. vector<vector<int> > words_cnt[1006];
  15. int dp[10005];
  16. bool compare_two_strings(string &A, string &B) {
  17.  
  18.   return true;
  19. }
  20.  
  21.  
  22. int backtrack[10005];
  23.  
  24. int dinamicko(int i){
  25. if(i==n){
  26.     backtrack[i] = -1;
  27.     return 0;
  28. }
  29.     if(dp[i] != -1) {
  30.         return dp[i];
  31.     }
  32. int result=-1;
  33.     int next_index = -1;
  34.     vector<int> cntA(26, 0);
  35.  
  36.  
  37.  
  38.    for(int j = 0; j < s[i].size(); j++) {
  39.         cntA[s[i][j] - 'A']++;
  40.     }
  41.    
  42.    
  43.     int k = s[i].size();
  44.    
  45.     for(int j = 0; j < words[k + 1].size(); j++) {
  46.         vector<int> cntB = words_cnt[k + 1][j];
  47.         bool ok = true, flag = false;
  48.         for(int l = 0; l < 26; l++) {
  49.             if(abs(cntA[l] - cntB[l]) == 0) continue;
  50.             if(abs(cntA[l] - cntB[l]) == 1 and  !flag) {
  51.                 flag = true;
  52.                 continue;
  53.             }
  54.             if(abs(cntA[l] - cntB[l]) >= 1 or flag) {
  55.                 ok = false;
  56.                 break;
  57.             }
  58.         }
  59.         if(!ok) continue;
  60.             int tmp = dinamicko(words[k + 1][j].second) + 1;
  61.             if(tmp > result) {
  62.                 result = tmp;
  63.                 next_index = words[k + 1][j].second;
  64.             }
  65.        
  66.     }
  67.     if(next_index != -1)
  68.         backtrack[i] = next_index;
  69.  
  70.  
  71.     return dp[i] = result;
  72. }
  73. int main()
  74. {
  75.     ios_base::sync_with_stdio(false);
  76.     ifstream cin("input.txt");
  77.     memset(dp, -1, sizeof dp);
  78. cin>>n;
  79.  
  80. for(int i=0; i<n; i++){
  81.     string a;
  82.     cin>>a;
  83. //    sort(a.begin(), a.end());
  84.     s.push_back(a);
  85.     vector<int> alpha(26, 0);
  86.     for(int j = 0; j < a.size(); j++) {
  87.         alpha[a[j] - 'A']++;
  88.     }
  89.     words[(int) a.size()].push_back(make_pair(a, i));
  90.     words_cnt[(int) a.size()].push_back(alpha);
  91. }
  92.    
  93. //    sort(s.begin(), s.end());
  94.     memset(backtrack, -1, sizeof backtrack);
  95.     int result = -1;
  96.     int START = 0;
  97.     for(int i = 0; i < n; i++) {
  98.         int tmp =  dinamicko(i) ;
  99.        
  100.         if(result < tmp and s[i].size() <= 2) {
  101.             result = tmp;
  102.             START = i;
  103.         }
  104.     }
  105.     cout << result << endl;
  106. //    cout << s[START] << endl;
  107. //    if(result <= 1) {
  108. //        cout << 1 << endl;
  109. //        cout << s[0][0] << endl;
  110. //        return 0;
  111. //    }
  112. //    set<string> st;
  113.     string p = "";
  114.     p += s[START][0];
  115.     vector<string> ret;
  116.     ret.push_back(p);
  117.     if(s[START].size() == 1) {
  118.         ret.erase(ret.begin());
  119.     }
  120. //    st.insert(p);
  121.     while(START != -1) {
  122. //        st.insert(s[START]);
  123.         ret.push_back(s[START]);
  124.         START = backtrack[START];
  125.     }
  126. //    cout << START << endl;
  127. //    cout << s[START] << endl;
  128.     if(ret[0].size() != ret[1].size() - 1) {
  129.         cout << 1  << "\nA";
  130.         return 0;
  131.     }
  132.     cout << ret.size() << endl;
  133.    
  134.     for(string x : ret) {
  135.         cout << x << "\n";
  136.     }
  137.     return 0;
  138. }
  139.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement