CodeForces - 1303E Erase Subsequences

传送门：CodeForces - 1303E

思路分析

两个字符串S和T，能否从S中最多选择两个不想交的子序列拼成T
看数据范围可以想到$n^3$的算法
因为是可以由两个子序列拼接，所以可以通过枚举T的分割点进行dp
设dp[i][j]表示该用第i个字母，并且已经匹配了$t_1$字符串的第j个位置,$t_2$最多匹配到哪一个

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;

int dp[444][444];


bool check(string s,string t) {
    int cnt=0;
    for(int i=0; i<s.size(); i++)
        if(s[i]==t[cnt])
            cnt++;
    return cnt>=t.size();
}

bool go(string s,string t1,string t2) {
    mem(dp,-1);
    dp[0][0]=0;
    for(int i=0; i<s.size(); i++) {
        for(int j=0; j<=t1.size(); j++) {
            if(dp[i][j]<0)continue;

            if(j<t1.size() && s[i]==t1[j])
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);

            if(dp[i][j]<t2.size() && s[i]==t2[dp[i][j]])
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]+1);

            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
        }
    }

    int f1=dp[s.size()][t1.size()];
    int f2=t2.size();
    if(f1>=f2)
        return true;
    else
        return false;
}

bool solve() {
    string s,t;
    cin>>s>>t;
    if(check(s,t))
        return true;
    for(int i=1; i<=t.size()-1; i++)
        if(go(s,t.substr(0,i),t.substr(i)))
            return true;

    return false;
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--) {
        if(solve())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }



    return 0;
}