Advertisement
Josif_tepe

Untitled

Nov 3rd, 2022
1,329
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1.    
  2.     #include <iostream>
  3.     #include <vector>
  4.     #include <fstream>
  5.     #include <algorithm>
  6. #include <cstring>
  7.     using namespace std;
  8.     int memo[10005];
  9.     int n;
  10.     vector<pair<pair<int, string>, vector<int> > > v;
  11. int backtrack[10005];
  12.     int dp(int index){
  13.         if(index == n){
  14.             return 0;
  15.         }
  16.         if(memo[index] != -1){
  17.             return memo[index];
  18.         }
  19.         int res = 0;
  20.         vector<int> a1;
  21.         vector<int> b1;
  22.         for (int i = index+1; i < v.size()  ; i++) {
  23.             if(v[i].first.first == v[index].first.first + 1){
  24.                 bool ok = false;
  25.                 bool moze = true;
  26.                 a1 = v[i].second;
  27.                 b1 = v[index].second;
  28.                 for (int j = 0; j < 26; j++) {
  29.                     if(a1[j] != b1[j] && ok == false){
  30.                        if(abs(a1[j] - b1[j]) == 1){
  31.                             ok = true;
  32.                        }
  33.                        else
  34.                            moze = false;
  35.                     }
  36.                     else if(a1[j] != b1[j] && ok == true){
  37.                         moze = false;
  38.                         break;
  39.                     }
  40.  
  41.                 }
  42.                if(moze){
  43.                    if(res < dp(i) + 1) {
  44.                        res = dp(i) + 1;
  45.                        backtrack[index] = i;
  46.                    }
  47.                }
  48.             }
  49.         }
  50.         return memo[index] = res;
  51.     }
  52.  
  53.     int main()
  54.     {
  55.  
  56.         cin >> n;
  57.         memset(backtrack, -1, sizeof backtrack);
  58.         for(int i = 0; i < n; i++) {
  59.             string s;
  60.             cin >> s;
  61.             vector<int> cnt(26, 0);
  62.             for(int j = 0; j < s.size(); j++) {
  63.                 cnt[s[j] - 'A']++;
  64.             }
  65.             v.push_back(make_pair(make_pair(s.size(), s), cnt));
  66.         }
  67.         sort(v.begin(), v.end());
  68.         memset(memo, -1,sizeof memo);
  69.         int result = 0, start_id = 0;
  70.        
  71.         for(int i =0 ; i < n; i++) {
  72.             if(v[i].first.first == 2) {
  73.                 if(result < dp(i)) {
  74.                     result = dp(i) + 1;
  75.                     start_id = i;
  76.                 }
  77.             }
  78.         }
  79. //        cout << result << endl;
  80.         if(result <= 1) {
  81.             cout << 1 << "\n";
  82.             cout << "A" << endl;
  83.             return 0;
  84.         }
  85.         vector<string> ans;
  86.         ans.push_back(string() + v[start_id].first.second[0]);
  87.        
  88.         int A = start_id;
  89.         while(A != -1) {
  90.             ans.push_back(v[A].first.second);
  91.             A = backtrack[A];
  92.         }
  93.         if(ans[0].size() == ans[1].size()) {
  94.             ans.erase(ans.begin());
  95.         }
  96.         cout << ans.size() << "\n";
  97.         for(int i = 0; i < ans.size(); i++) {
  98.             cout << ans[i] << "\n";
  99.         }
  100.         return 0;
  101.     }
  102.  
  103.  
  104.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement