Question:
现有一个主串S 和 三个空串 A,B,C(只含小写字母)。问每次操作后 S 是否能包含 A B C (在保证 A B C 串内字母顺序不变的情况下组成S的一个子序列)
操作是在某个串后面添加或删除字母
一共q次操作
|A| ,|B| ,|C| <= 250 。|S| <= 100000 。 q<1000
我们要及时发现题目特点来确定解法 去主动猜测这题该怎么去做 要大胆假设,细心实现
Solution:
发现串a,b,c <= 250 那么可以建立一个dp数组 DP[i] [j] [k] 表示 A串匹配前 i 个, B 串匹配前 j 个 ,c k 个 时在串S上的最小长度 这样每次判断时候 只需判断 dp[la][lb][lc] 是否小于 n 即可 并能得到转移方程
dp[i][j][k]=min(dp[i][j][k],nt[dp[i-1][j][k]][a[i]-'a']);
dp[i][j][k]=min(dp[i][j][k],nt[dp[i][j-1][k]][b[j]-'a']);
dp[i][j][k]=min(dp[i][j][k],nt[dp[i][j][k-1]][c[k]-'a']);
如果每次都暴力转移方程,那么时间复杂度会达到O(250^3*q)
仔细想想其实发现每次都只是将一个串的长度+1 那么就不需要 重复计算已经算过的了。每次转移只需要O(250^2)即可 其中预处理nt【i】【j】数组加速 表示 S 第i个位置后面第一次出现字符j的位置
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define warn printf("!!!***!\n")
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int maxn=2e6+6;
const int oo=0x3fffffff;
const int mod=1e9+7;
int n,q,la,lb,lc,p,len,nt[100100][30],pos[30],dp[255][255][255];
char s[maxn],a[maxn],b[maxn],c[maxn],op,typ;
int main()
{
ios::sync_with_stdio(0);
cin>>n>>q>>s+1;
rep(i,0,25) pos[i]=n+1;
rep(i,0,25) nt[n+1][i]=n+1;
per(i,n,0){
rep(j,0,25) nt[i][j]=pos[j];
pos[s[i]-'a']=i;
}
while(q--){
cin>>op>>p;
if(op=='+'){
cin>>typ;
if(p==1) a[++la]=typ;
if(p==2) b[++lb]=typ;
if(p==3) c[++lc]=typ;
rep(i,p==1?la:0,la){
rep(j,p==2?lb:0,lb){
rep(k,p==3?lc:0,lc){
dp[i][j][k]=n+1;
//cout<<i<<','<<j<<','<<k<<','<<nt[dp[i][j][k]][a[i]-'a']<<','<<dp[i][j][k]<<endl;
if(i)dp[i][j][k]=min(dp[i][j][k],nt[dp[i-1][j][k]][a[i]-'a']);
//cout<<i<<','<<j<<','<<k<<','<<nt[dp[i-1][j][k]][a[i]-'a']<<','<<dp[i][j][k]<<endl;
if(j)dp[i][j][k]=min(dp[i][j][k],nt[dp[i][j-1][k]][b[j]-'a']);
//cout<<i<<','<<j<<','<<k<<','<<nt[dp[i][j-1][k]][a[i]-'a']<<','<<dp[i][j][k]<<endl;
if(k)dp[i][j][k]=min(dp[i][j][k],nt[dp[i][j][k-1]][c[k]-'a']);
//cout<<i<<','<<j<<','<<k<<','<<nt[dp[i][j][k-1]][a[i]-'a']<<','<<dp[i][j][k]<<endl;
}
}
}
}
else {
if(p==1) la--;
if(p==2) lb--;
if(p==3) lc--;
}
if(dp[la][lb][lc]<=n) {
printf("YES\n");
}
else printf("NO\n");
/* 6 8 abbaab + 1 a + 2 a + 3 a + 1 b + 2 b + 3 b - 1 + 2 z */
}
}