【CodeForces 163A】 Substring and Subsequence

印象中好像是唯一一道自己做对的除背包以外的线性 DP 题(我太菜了 QAQ),因此想写篇题解纪念一下

题目大意

题目传送门

翻译有点问题,我这里重新翻一下

大概意思就是说,给你两个字符串sstt,求出有多少对字符串xxyy,满足xxss的子串且yytt的子序列,答案对1000000007(109+7)1000000007(10^9+7)取模

关于子串和子序列的区别,可以理解为子串是一段连续的区间,而子序列则不一定是连续的

思路

这道题乍一看其实很像最长公共子序列,唯一不同的在于对于ss要取它的子串,我们类比一下最长公共子序列的状态转移方程

dp[i,j]={0 (i=0 or j=0)dp[i1,j1]+1 (s[i]=t[j])max(dp[i1,j],dp[i,j1]) (s[i]t[j])dp[i,j]=\begin{cases}0\ (i=0 \text{ or }j=0)\\dp[i-1,j-1]+1\ (s[i]=t[j])\\\max(dp[i-1,j],dp[i,j-1])\ (s[i]\not =t[j])\end{cases}

dp[i,j]dp[i,j]表示的是在ss的前ii个字符和tt的前jj个字符中的最长公共子序列的长度,因此,对于这道题,我们不妨设dp[i,j]dp[i,j]ss的第ii个字符为结尾的子串与tt的前jj个字符中的子序列相同的个数,同样,我们分成两种情况来讨论,一种是s[i]=t[j]s[i]=t[j],一种是s[i]t[j]s[i]\not =t[j]

如果s[i]=t[j]s[i]=t[j],那么当前状态首先应该包括了dp[i1,j1]dp[i-1,j-1]的所有情况,因为这两个字符是相同的,那么我们相当于是可以在dp[i1,j1]dp[i-1,j-1]的所有情况后面加上一个相同的字符,结果一定还是成立的,然后还应该包括dp[i,j1]dp[i,j-1]的所有情况,因为不管当前两个字符是否相同,dp[i,j1]dp[i,j-1]的所有情况肯定都适用于dp[i,j]dp[i,j],最后,dp[i,j]dp[i,j]还应该包括s[i]s[i]t[j]t[j]这对组合,因为很明显前面两种情况都没有把t[j]t[j]算进去,所以最后的状态转移方程应该是这样的

dp[i,j]=dp[i,j1]+dp[i1,j1]+1dp[i,j]=dp[i,j-1]+dp[i-1,j-1]+1

如果s[i]t[j]s[i]\not = t[j],那么上面所说的dp[i1,j1]dp[i-1,j-1]的情况就不适用于当前情况,也没有s[i]s[i]t[j]t[j]这对组合,所以状态转移方程就是这样的

dp[i,j]=dp[i,j1]dp[i,j]=dp[i,j-1]

最后,由于dp[i,j]dp[i,j]只统计了以s[i]s[i]为结尾的子串,所以最终答案应该把所有的dp[i,s]dp[i,|s|]加起来,另外,不要忘记取模

参考代码

其实只要搞清楚状态转移方程了,代码什么的就很好写了,这就是你懒得写注释的理由吗!,关键是要理解思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
string a,b;
int n,m,ans,dp[5001][5001];
int main()
{
getline(cin,a);
getline(cin,b);
n=a.length();
m=b.length();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i-1]==b[j-1])
dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]+1)%mod;//取模!!
else
dp[i][j]=dp[i][j-1];
for(int i=1;i<=n;i++)
ans=(ans+dp[i][m])%mod;
printf("%d",ans);
return 0;
}

【CodeForces 163A】 Substring and Subsequence

http://www.azusemisa.top/posts/3005834406.html

作者

AzuSemisa

发布于

2020-07-31

更新于

2020-08-23

许可协议

评论