Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- #include <algorithm>
- #include <fstream>
- #include <cstring>
- #include <set>
- //#include <bits/stdc++.h>
- using namespace std;
- vector<string>s;
- int n;
- vector<pair<string, int> > words[1005];
- vector<vector<int> > words_cnt[1006];
- int dp[10005];
- bool compare_two_strings(string &A, string &B) {
- return true;
- }
- int backtrack[10005];
- int dinamicko(int i){
- if(i==n){
- backtrack[i] = -1;
- return 0;
- }
- if(dp[i] != -1) {
- return dp[i];
- }
- int result=-1;
- int next_index = -1;
- vector<int> cntA(26, 0);
- for(int j = 0; j < s[i].size(); j++) {
- cntA[s[i][j] - 'A']++;
- }
- int k = s[i].size();
- for(int j = 0; j < words[k + 1].size(); j++) {
- vector<int> cntB = words_cnt[k + 1][j];
- bool ok = true, flag = false;
- for(int l = 0; l < 26; l++) {
- if(abs(cntA[l] - cntB[l]) == 0) continue;
- if(abs(cntA[l] - cntB[l]) == 1 and !flag) {
- flag = true;
- continue;
- }
- if(abs(cntA[l] - cntB[l]) >= 1 or flag) {
- ok = false;
- break;
- }
- }
- if(!ok) continue;
- int tmp = dinamicko(words[k + 1][j].second) + 1;
- if(tmp > result) {
- result = tmp;
- next_index = words[k + 1][j].second;
- }
- }
- if(next_index != -1)
- backtrack[i] = next_index;
- return dp[i] = result;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- ifstream cin("input.txt");
- memset(dp, -1, sizeof dp);
- cin>>n;
- for(int i=0; i<n; i++){
- string a;
- cin>>a;
- // sort(a.begin(), a.end());
- s.push_back(a);
- vector<int> alpha(26, 0);
- for(int j = 0; j < a.size(); j++) {
- alpha[a[j] - 'A']++;
- }
- words[(int) a.size()].push_back(make_pair(a, i));
- words_cnt[(int) a.size()].push_back(alpha);
- }
- // sort(s.begin(), s.end());
- memset(backtrack, -1, sizeof backtrack);
- int result = -1;
- int START = 0;
- for(int i = 0; i < n; i++) {
- int tmp = dinamicko(i) ;
- if(result < tmp and s[i].size() <= 2) {
- result = tmp;
- START = i;
- }
- }
- cout << result << endl;
- // cout << s[START] << endl;
- // if(result <= 1) {
- // cout << 1 << endl;
- // cout << s[0][0] << endl;
- // return 0;
- // }
- // set<string> st;
- string p = "";
- p += s[START][0];
- vector<string> ret;
- ret.push_back(p);
- if(s[START].size() == 1) {
- ret.erase(ret.begin());
- }
- // st.insert(p);
- while(START != -1) {
- // st.insert(s[START]);
- ret.push_back(s[START]);
- START = backtrack[START];
- }
- // cout << START << endl;
- // cout << s[START] << endl;
- if(ret[0].size() != ret[1].size() - 1) {
- cout << 1 << "\nA";
- return 0;
- }
- cout << ret.size() << endl;
- for(string x : ret) {
- cout << x << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement