CF1303E - Erase Subsequences

제목의 뜻

두 문자열 ssss와 ttt, ssss의 교집합이 없는 두 개의 하위 문자열을 ttttt열로 연결하여 t=t1+t2t=t1+t2t=t1+t2,t1,t2t1,t2는 빈 문자열 1≤여t, 즉 t=t=t=t1 + t2 ttt2는 빈 문자열일 수 있음 1≤≤≤\87393939s\870≤4001\leq|t|||||||\leq|s||||||||||sqqqqqq4001≤\\\\\\Lqq 400 400 400400\\\\\\\\Lqq 400 400400\\\\\\\\\\\\\t

문제풀이

문자열의 길이를 보면 O(N3)O(N^3)O(N3)O(N3)의 가장 직접적인 생각은 tt열을 두 부분으로 나누어 t1, t2t1, t2t1, t2t1, t2t2, 그리고 ss열을 매칭하는 것이다. t1, t2t1, t2t1, t2t1을 보증한다. t2는 같은 문자를 쓰지 않고 f[i] [j] f[i] [j] f[j] f[i] [j]가 s[i] s[i] s[i] s[i] s[i] s[i] s[i] j] [t1] j] [t1] jt2] [t2] jt12] [t2] t12]의 위치를 매칭할 때 가장 큰 위치가 일치하는 것이다.마지막으로 f[|s|][|t1|]=\f[|s|][|t1|]=\f[|t1|][|t1|]=|t2|f[|s]]=\t2\는 상태 이동 방정식을 찾을 수 있음을 나타낸다.
①s[i]s[i]s[i]가 t1 t1 t1을 매칭했을 때 t1 t1 t1은 이미 jjj에 매칭됐고, 다음은 j+1 j+1 j+1 f[i] [j+1] = m ax(f[i] [j+1], f[i-1] [j]) f[i] [j] [j+1] =max(f[i] [j+1] [j+1] f[i]
② s[i]s[i]s[i]가 t2t2t2와 일치하면 t2t2t2가 f[i-31][j]f[i-1][j]f[i-31][j]로 일치하고,다음은 f [i-4-1] [j] + 1 f[i-1] [j] + 1 f[i-1] [i-1] [j] [j] + 1 고 f [i] [j] + 1 f[i] + 1 f[i] [i] [j] [j] [j] + (s[i] = t 1𕕧 + f [i-1] [j] + 1]) f [i] [i] [j] [i] [j] [j] [j]++ [i] + [i] = [i] [j] [i] [i] [j] [i] [i] [j] [i] [i-[i] [j] [j] [i] [i] [i] [i-[j] [j] [i] [i] [i-[i] [f=[j]+1]) f[i][j]=max(f[i][j], f[i-1][j]+(s[i]=t[\t1\+f[i-1][j]+1])는 일치하는 길이에 1을 더하고 같지 않으며 변하지 않습니다.

코드

#include 
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int MAX = 4e2 + 10;

int T, N, M;
char s[MAX], t[MAX];
int f[MAX][MAX];//f[i][j]  s    i, t1   j , t2       

void init() {
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= M; j++)
            f[i][j] = j == 0 ? 0 : -INF;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%s%s", s + 1, t + 1);
        N = strlen(s + 1), M = strlen(t + 1);
        int flag = 0;
        for (int pre = 0; pre < M; pre++) {//t1  
            int suf = M - pre;//t2  
            init();
            for (int i = 1; i <= N; i++) {
                for (int j = 0; j <= pre; j++)
                    if (f[i - 1][j] != -INF) {
                        // t1  
                        if (j < pre && s[i] == t[j + 1]) f[i][j + 1] = max(f[i][j + 1], f[i - 1][j]);
                        // t2  ,      +1
                        f[i][j] = max(f[i][j], f[i - 1][j] + (pre + f[i - 1][j] + 1 <= M && s[i] == t[pre + f[i - 1][j] + 1]));
                    }
            }
            if (f[N][pre] == suf) {
                flag = 1;
                break;
            }
        }
        printf("%s
", flag ? "YES" : "NO");
    }

    return 0;
}