C题LCS （构造）

首先将a,b,c排序一下，我们假设a是最大的，c是最小的，那么如果s1和s2的lcs是a,s2和s3的lcs是b，那假设a跟b毫无重叠，s1和s3的最小重叠长度也有a+b-n,如果a+b-n仍比c大，则无解，否则可以一步一步构造出来

先让所有全部加进c个'a'，然后变为a-c,b-c,0。再让三个字符串中的两个分别加上a-c,b-c就行了。最后，再让三个字符串加上n-size个不一样的字符，凑成n,就构造完了。

下面是代码

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
int dp[2005][2005];
using namespace std;

struct node {
    int v, k;
    string ans;
};

int LCS(string a, string b, int n) {
    memset(dp, 0, sizeof dp);
    int ans = 0;
    for(int i = 1; i <= a.size(); i++)
        for(int j = 1; j <= b.size(); j++){
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            if(a[i-1]==b[j-1]) dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);         
            }
    return dp[a.size()][b.size()];
}

void solve() {
    node p[3], a[3];
    int n;
    for (int i = 0; i < 3; ++i) {
        cin >> p[i].v;
        p[i].k = i;
        a[i] = p[i];
    }
    cin >> n;
    sort(p, p + 3, [](node a, node b) { return a.v < b.v;});
    if (p[2].v + p[1].v - n> p[0].v ) {
        cout << "NO" << endl;
    }else {
        for (int i = 0; i < p[0].v; ++i) {
            for (int j = 0; j < 3; ++j) {
                p[j].ans.push_back('a');
            }
        }
        for (int i = p[0].v; i < p[1].v; ++i) {
            p[1].ans.push_back('b');
            p[2].ans.push_back('b');
        }
        for (int i = p[0].v; i < p[2].v; ++i) {
            p[0].ans.push_back('c');
            p[2].ans.push_back('c');
        }
        for (int i = 0; i < 3; ++i) {
              while(p[i].ans.size()<n)    p[i].ans.push_back('d'+i);
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 3; ++k) {
                    if (i != j && j != k && i != k) {
                        if (LCS(p[i].ans, p[j].ans, n) == a[0].v && LCS(p[k].ans, p[j].ans, n) == a[1].v && LCS(p[i].ans, p[k].ans, n) == a[2].v) {
                            cout << p[i].ans << endl << p[j].ans << endl << p[k].ans << endl;
                            return;
                        }
                    }
                }
            }
        }
    }
}

int main() {
     solve();
}