Codeforces 1303E. Erase Subsequences 代码(dp 字符串压缩一维状态优化)
2024-09-05 10:43:48
https://codeforces.com/contest/1303/problem/E
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int dp[maxn][maxn];
bool check(string s,string t){
int indx = ;
for(int i = ;i<s.length();i++){
if(t[indx] == s[i]) indx++;
}
if(indx == t.length()) return true;
return false;
}
bool check(string s,string t1,string t2){
memset(dp,-,sizeof(dp));
dp[][] = ;
for(int i = ;i<s.length();i++){
for(int j = ;j<=t1.size();j++){
if(dp[i][j]<) continue;
if(j<t1.size() && s[i] == t1[j]){
dp[i+][j+] = max(dp[i+][j+],dp[i][j]);
}
if(dp[i][j]<t2.size() && s[i] == t2[dp[i][j]]){
dp[i+][j] = max(dp[i+][j],dp[i][j]+);
}
dp[i+][j] = max(dp[i+][j],dp[i][j]);
}
}
if(dp[s.length()][t1.length()] == t2.length()) return true;
return false;
}
void solve(){
string s,t;
cin>>s>>t;
if(check(s,t)){
cout<<"YES"<<endl;
return;
}
for(int i = ;i<t.length()-;i++){
string t1 = t.substr(,i+);
string t2 = t.substr(i+,t.size());
if(check(s,t1,t2)){
cout<<"YES"<<endl;
return;
}
}
cout<<"NO"<<endl;
return;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return ;
}
最新文章
- GO语言总结(3)——数组和切片
- getAttribute、setAttribute、removeAttribute
- 1、Hadoop的伪分布式部署
- 用函数生成select选择框
- 在SQL中修改数据库名称
- 响应式布局—设备像素密度测试 (-webkit-min-device-pixel-ratio)
- JNI 方法注册与签名+BufferedReader使用readLine问题
- CAS单点登录入门
- mysql建表时
- android 知识汇总
- vue移动端金融UI组件库滴滴MandMobile面向金融场景设计附功能思维导图
- windows下telnet不是内部或外部命令
- agc023C - Painting Machines(组合数)
- 05_ssm基础(六)之SpringMVC
- 单点登录--CAS认证--web.xml配置详解
- (转载)220v交流接触器自锁接线图另接热继电器
- Python -- 图片处理
- Flutter Stack布局中定位的方式
- 使用JSONP彻底解决Ajax跨域访问Cookie Session的方案
- Docker - 容器中的tomcat如何使用startup.sh启动