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];
- 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(26, 0);
- for(int l = 0; l <words[k + 1][j].first.size(); l++) {
- cntB[words[k + 1][j].first[l] - 'A']++;
- }
- bool ok = true;
- for(int l = 0; l < 26; l++) {
- if(cntA[l] > cntB[l]) {
- 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);
- words[(int) a.size()].push_back(make_pair(a, i));
- }
- // sort(s.begin(), s.end());
- memset(backtrack, -1, sizeof backtrack);
- int result = 0;
- int START = 0;
- for(int i = 0; i < n; i++) {
- int tmp = dinamicko(i) + 1;
- if(result < tmp) {
- result = tmp;
- START = i;
- }
- }
- 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];
- }
- if(ret[0].size() != ret[1].size() - 1) {
- cout << 1 << "\nA";
- return 0;
- }
- cout << st.size() << endl;
- for(string x : ret) {
- cout << x << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement