Codeforces Contest 1150 D Three Religions —— DP求三个子序列能否构成字符串的子序列

本文主要是介绍Codeforces Contest 1150 D Three Religions —— DP求三个子序列能否构成字符串的子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一个总的字符串，然后现在有三个空字符串，有q次操作，每次操作都会往三个字符串某一个字符串的末尾添加或者删除一个字符，问你这三个字符串按照他们的序列方式拼在一起能否组成总的字符串中的某一个序列。

题解：

最近脑子不好了，已经想不到三个序列如何拼成大的序列了，其实很简单，因为三个序列最大每个序列只有250的长度。
我们设dp[i][j][k]表示第一个串到第i位，第二个字符串到第j位，第三个字符串到第k位的时候在总的字符串中的最小位置。
那么当第1个字符串添加了一位的时候，我们只需要 $n^2$ 做一下dp[i+1][j][k]即可。正确性：
假设现在有一个位置x满足dp[i][j][k]，有另外一个位置x+a满足dp[i][j][k]，那么对于下一个字符来说，x更优。
那么状态转移方程之一：

dp[i][j][k]=min(dp[i][j][k],nex[dp[i-1][j][k]+1][ss[1][i]-'a']);

为什么是dp[i-1][j][k]+1呢，如果j+1在dp[i-1][j][k]之前不是就错了吗：
在这里插入图片描述
那么这种情况再枚举到j+1且未枚举到k的时候会被记录下来，所以不会有问题

#include<bits/stdc++.h>
using namespace std;
const int N=251;
int dp[N][N][N],nex[100005][26],len[3];
char s[100005],ss[4][N];
int main()
{int n,q;scanf("%d%d%s",&n,&q,s+1);for(int i=0;i<26;i++)nex[n+1][i]=nex[n+2][i]=n+1;for(int i=n;i>=0;i--)for(int j=25;j>=0;j--)nex[i][j]=s[i]-'a'==j?i:nex[i+1][j];while(q--){char op[2];int id;scanf("%s%d",op,&id);if(op[0]=='+'){scanf("%s",op);ss[id][++len[id]]=op[0];for(int i=id==1?len[1]:0;i<=len[1];i++){for(int j=id==2?len[2]:0;j<=len[2];j++){for(int k=id==3?len[3]:0;k<=len[3];k++){dp[i][j][k]=i==0&&j==0&&k==0?0:n+1;if(i)dp[i][j][k]=min(dp[i][j][k],nex[dp[i-1][j][k]+1][ss[1][i]-'a']);if(j)dp[i][j][k]=min(dp[i][j][k],nex[dp[i][j-1][k]+1][ss[2][j]-'a']);if(k)dp[i][j][k]=min(dp[i][j][k],nex[dp[i][j][k-1]+1][ss[3][k]-'a']);}}}}elselen[id]--;if(dp[len[1]][len[2]][len[3]]<=n)printf("YES\n");elseprintf("NO\n");}return 0;
}

这篇关于Codeforces Contest 1150 D Three Religions —— DP求三个子序列能否构成字符串的子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！