D. Shortest Common Non-Subsequence // DP, 最小字典序

求两个字符串的 最短的 公共的 非子序列.即该序列不是A的子序列也不是B的子序列

分析

考虑填答案DP. 设输入字符串分别为 s , t . 答案为 q.

对于最后的答案, 由于它是最短的, 所以把他删掉最后一位之后, 它或者是 s 的子序列, 或者是 t 的子序列.
从空的答案开始.

如果 q 的第一个位置是0. 那么就会匹配到 s 的第一个0 和 t 的第一个 0.

否则 q 的第一个位置是1. 那么就会匹配到 s 的第一个1 和 t 的第一个 1.

然后考虑第二个位置, 如果是 0, 那么就会匹配到下一个0.

这样一直匹配下去.直到最后匹配到 s 的末尾的后一位, t 的末尾的后一位, 这时候的 q 是 s,t 的公共非子序列.

最小字典序: 这题还要一个最小字典序. dp 的时候从后往前遍历. $dp[len(s) + 1][len(t) + 1] = 0$ . 最后答案即为 $dp[0][0]$ .

然后再从 $dp[0][0]$ 出发, 从前往后, 先看一下能不能从下一个 $0$ 转移过来, 如果可以就 $0$ 转移. 否则选 $1$ 转移. 这样就可以得到最小的字典序l

#include <bits/stdc++.h>
using namespace std;

const int N = 4e3 + 5, INF = 0x3f3f3f3f;

typedef pair<int, int> pii;
typedef long long LL;

int suf[2][N][2];
char s[2][N];
int dp[N][N], ans[N][N], last0, last1;
int main()
{
    scanf("%s %s", s[0]+1, s[1]+1);
    int len[2];
    len[0] = strlen(s[0]+1);
    len[1] = strlen(s[1]+1);
    for (int i = 0; i <= 1; i++) { // 预处理0和1的位置
        last0 = last1 = len[i] + 1;
        for (int j = len[i] + 1; j >= 0; j--) {
            suf[i][j][0] = last0;
            suf[i][j][1] = last1;
            if (s[i][j] == '1') last1 = j;
            else last0 = j;
        }
    }
    memset(dp, INF, sizeof(dp));
    dp[len[0] + 1][len[1] + 1] = 0;
    for (int i = len[0] + 1; i >= 0; i--) {
        for (int j = len[1] + 1; j >=0 ; j--) {
            int x, y;
            x = suf[0][i][0]; // 填0
            y = suf[1][j][0];
            if (dp[x][y] + 1 < dp[i][j] || dp[i][j] == dp[x][y] + 1 && ans[x][y] == 1) {
                ans[x][y] = 0;
                dp[i][j] = dp[x][y] + 1;
            }
            x = suf[0][i][1];  // 填1
            y = suf[1][j][1];
            if (dp[x][y] + 1 < dp[i][j]) {
                ans[x][y] = 1;
                dp[i][j] = dp[x][y] + 1;
            }
        }
    }
    vector<int> aans;
    int x = 0, y = 0;
    for (int i = 1; i <= dp[0][0]; i++) {
        int nx, ny;
        nx = suf[0][x][0];
        ny = suf[1][y][0];
        if (dp[nx][ny] == dp[x][y]-1) {
            x = nx;
            y = ny;
            aans.push_back(0);
            continue;
        }
        nx = suf[0][x][1];
        ny = suf[1][y][1];
        x = nx, y = ny;
        aans.push_back(1);
    }
    for (auto x:aans) printf("%d", x);
    return 0;
}