Advertisement
Josif_tepe

Untitled

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