Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- int memo[10005];
- int n;
- vector<pair<pair<int, string>, vector<int> > > v;
- int backtrack[10005];
- int dp(int index){
- if(index == n){
- return 0;
- }
- if(memo[index] != -1){
- return memo[index];
- }
- int res = 0;
- vector<int> a1;
- vector<int> b1;
- for (int i = index+1; i < v.size() ; i++) {
- if(v[i].first.first == v[index].first.first + 1){
- bool ok = false;
- bool moze = true;
- a1 = v[i].second;
- b1 = v[index].second;
- for (int j = 0; j < 26; j++) {
- if(a1[j] != b1[j] && ok == false){
- if(abs(a1[j] - b1[j]) == 1){
- ok = true;
- }
- else
- moze = false;
- }
- else if(a1[j] != b1[j] && ok == true){
- moze = false;
- break;
- }
- }
- if(moze){
- if(res < dp(i) + 1) {
- res = dp(i) + 1;
- backtrack[index] = i;
- }
- }
- }
- }
- return memo[index] = res;
- }
- int main()
- {
- cin >> n;
- memset(backtrack, -1, sizeof backtrack);
- for(int i = 0; i < n; i++) {
- string s;
- cin >> s;
- vector<int> cnt(26, 0);
- for(int j = 0; j < s.size(); j++) {
- cnt[s[j] - 'A']++;
- }
- v.push_back(make_pair(make_pair(s.size(), s), cnt));
- }
- sort(v.begin(), v.end());
- memset(memo, -1,sizeof memo);
- int result = 0, start_id = 0;
- for(int i =0 ; i < n; i++) {
- if(v[i].first.first == 2) {
- if(result < dp(i)) {
- result = dp(i) + 1;
- start_id = i;
- }
- }
- }
- // cout << result << endl;
- if(result <= 1) {
- cout << 1 << "\n";
- cout << "A" << endl;
- return 0;
- }
- vector<string> ans;
- ans.push_back(string() + v[start_id].first.second[0]);
- int A = start_id;
- while(A != -1) {
- ans.push_back(v[A].first.second);
- A = backtrack[A];
- }
- if(ans[0].size() == ans[1].size()) {
- ans.erase(ans.begin());
- }
- cout << ans.size() << "\n";
- for(int i = 0; i < ans.size(); i++) {
- cout << ans[i] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement