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

제목 링크 제목: 두 문자열 s,ts,t,t를 드립니다. ttt는 ss의 서로 교차하지 않는 두 서열로 구성될 수 있는지 물어보세요.사고방식: 분명히 우리는 tt의 단점 iii를 매거해야 한다. [1,i][1,i][1,i]를 하위 서열 [i+1,l ent] [i+1,len t] [i+1,lent]를 두 번째 하위 서열로 해야 한다.그리고 check 이런 상황이 합법적인지 아닌지.우리는 앞의 절반은 L L L이고 뒤의 절반은 R R R R R d p [i] [j] dp[i] [j] dp[i] [j]로 설정하여 현재 L i와 일치하고 R j Li,R_j Li, Rj가 s s s에서 가장 작은 위치입니다.d p [l e n L] [l e n R] < = l e n s dp [len L] [len R] <=lensdp[lenL][lenR]<=lens는 합법적입니다.이동용 서열 자동기를 최적화하면 된다.세부적인 문제에 주의해라.

#include 
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<
        break;
      }
    }
    if(ok)cout<<"YES
";
    else cout<<"NO
";
  }
  return 0;
}