CCCPaste

Untitled

#include 
#include 
#include 
using namespace std;

int n;
pair > v[10005];
vector, vector > > g[1005];
int dp[10005];
int backtrack[10005];
int f(int at)
{
    if(dp[at] != -1) {
        return dp[at];
    }
    int result = 0;
    int sz = (int) v[at].first.size();
    int max_result = 0;
    for(int i = 0; i < (int) g[sz + 1].size(); i++) {
        string tmp = g[sz + 1][i].first.first;
        vector cnt1 = v[at].second;
        vector cnt2 = g[sz + 1][i].second;
        bool flag = false, ok = true;
        for(int j = 0; j < 26; j++) {
            if(abs(cnt1[j] - cnt2[j]) == 1 and !flag) {
                flag = true;
                continue;
            }
             if(abs(cnt1[j] - cnt2[j]) > 0) {
                ok = false;
                break;
            }
        }
        if(ok) {
            result = f(g[sz + 1][i].first.second) + 1;
            if(result > max_result) {
                max_result = result;
                backtrack[at] = g[sz + 1][i].first.second;
            }
        }
    }
    return dp[at] = max_result;
}
int main()
{
    ios_base::sync_with_stdio(false);
    memset(dp, -1, sizeof dp);
    memset(backtrack, -1, sizeof backtrack);
    cin>>n;
    for(int i = 0; i < n; i++) {
        cin >>v[i].first;

        vector cnt(26, 0);
        
        for(int j = 0; j < (int) v[i].first.size(); j++) {
            cnt[v[i].first[j] - 'A']++;
        }
        v[i].second = cnt;
        g[(int)v[i].first.size()].emplace_back(make_pair(make_pair(v[i].first, i), cnt));
      
    }
    int result = 0, idx = 0;
    for(int i = 0; i < n; i++) {
        if((int) v[i].first.size() <= 2 and f(i) + 1 > result) {
            result = f(i) + 1;
            idx = i;
        }
    }
    
    if(result <= 1) {
        cout << 1 << endl;
        cout << "A" << endl;
        return 0;
    }
    vector answer;
    answer.push_back(string() + v[idx].first[0]);
    if(v[idx].first.size() != 1) {
        answer.push_back(v[idx].first);
    }
    idx = backtrack[idx];
    while(idx != -1) {
        answer.push_back(v[idx].first);
        idx = backtrack[idx];
    }
    
    cout << answer.size() << endl;
    for(int i =0 ; i < (int) answer.size(); i++) {
        cout << answer[i] << "\n";
    }
    return 0;
}