Educational Codeforces Round 82 (Rated for Div. 2)E. Erase Subsequences

题目链接
题意：给你两个字符串 $s,t$s,t，问你 $t$t是否可以由 $s$s的两个不相交子序列构成。
思路：显然我们应该枚举 $t$t的断点 $i$i，使得 $[1,i]$[1,i]为一个子序列 $[i+1,le{n}_t]$[i+1,lent​]为第二个子序列。然后check这种情况是否合法.我们设前一半为 $L$L，后一半为 $R$R
$dp\left[i\right]\left[j\right]$dp[i][j]表示当前匹配到 $L_i,R_j$Li​,Rj​在 $s$s中的最小位置。
若 dp[lenL​][lenR​]<=lens​即合法。
转移用序列自动机优化一下即可.
注意一下细节问题.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t;
char a[N],b[N];
int dp[403][403];
int nx[555][26];
int main() {
  ios::sync_with_stdio(false);
  for(cin>>t;t;t--){
    cin>>a+1>>b+1;
    int l=strlen(a+1);
    int r=strlen(b+1);
    for(int i=0;i<26;i++)nx[l+1][i]=nx[l+2][i]=l+1;
    for(int i=l;i>=1;i--){
      for(int j=0;j<26;j++)nx[i][j]=nx[i+1][j];
      nx[i][a[i]-'a']=i;
    }
    int ok=0;
    for(int i=0;i<r;i++){
      memset(dp,-1,sizeof dp);
      dp[0][i]=0;
      for(int j=0;j<=i;j++){
        for(int k=i;k<=r;k++){
          if(j==0&&k==i)
            continue;
          dp[j][k]=l+1;
          if(j) dp[j][k]=min(dp[j][k],nx[dp[j-1][k]+1][b[j]-'a']);
          if(k>i)dp[j][k]=min(dp[j][k],nx[dp[j][k-1]+1][b[k]-'a']);
        }
      }
      if(dp[i][r]<=l){
        ok=1;
        //cout<<i<<' '<<r<<' '<<dp[i][r]<<endl;
        break;
      }
    }
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";
  }
  return 0;
}