Senior's String

Accepts: 30

Submissions: 286

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

学姐姐非常喜欢字符串，所以学弟送给了她两个字符串作为礼物。

两个字符串分别为X，Y。她非常开心，但在开心之余她还想考考学弟。

她定义L为X与Y的最长公共子序列的长度（子序列在字符串内不一定连续，一个长度为L的字符串有2L个子序列，包括空子序列）。

现在学姐姐取出了X的所有长度为L的子序列，并要求学弟回答在这些子序列中，有多少个是Y的子序列。

因为答案可能很大，所以学弟只需要回答最终答案模109+7。

输入描述

第一行包含一个整数T，表示测试数据组数。

对于每组测试数据：

第一行包含一个非空字符串X。

第二行包含一个非空字符串Y。

字符串由小写英文字母构成。

1≤|X|,|Y|≤1000, |X|表示X的长度。

输出描述

对于每组测试数据输出一个整数，表示对应的答案。

输入样例

2

a

b

aa

ab

输出样例

1

2

题解：

首先我们用O(n2)的动态规划算法处理出dp数组，dp[i][j]表示X串的前i个字符和Y串的前j个字符的最长公共子序列的长度，在这个基础上我们再进行一个动态规划。用f[i][j]表示在X串的前i个字符中，有多少个长度为dp[i][j]的子序列在Y的前j个字符中也出现了。转移：若dp[i−1][j]==dp[i][j]，则f[i][j]+=f[i−1][j]，表示i这个字符不选；再考虑选i这个字符，找到Y串前j个字符中最靠后的与X[i]匹配的字符的位置，设为p，若dp[i−1][p−1]+1==dp[i][j]，则f[i][j]+=f[i−1][p−1]。最终的答案即为f[n][m]。复杂度O(n2)。

看着题解给的思路，想不明白。

然后又用到了两重动态规划，第一个很好理解，第二个其实就是对于每一个字符串x的字符，看它在不在长度为L“相等”的子序列里面，不在的话是第一种，在的话(即与x字符串之前的字符重复)是第二种。

代码：

#include <iostream>

#include <string>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int mod=1000000007;

int dp[1003][1003];

int f[1007][1007];

int meet[1007][27];

string x,y;

int main()

{

	int Test,m,n,i,j;

	cin>>Test;

	while(Test--)

	{

		cin>>x>>y;

		m=x.length();

		n=y.length();

		memset(dp,0,sizeof(dp));

		for(i=0;i<m;i++)

		{

			for(j=0;j<n;j++)

			{

				if(x[i] == y[j])

				{

					dp[i+1][j+1] = dp[i][j]+1;

				}

				else

				{

					dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);

				}

			}

		}

		memset(f,0,sizeof(f));

		memset(meet,0,sizeof(meet));

		for(i=0;i<n;i++)

		{

			for(j=0;j<26;j++)

			{

				meet[i+1][j] = meet[i][j];

			}

			meet[i+1][y[i]-'a']=i+1;

		}

		for(i=0;i<=m;i++)

		{

			for(j=0;j<=n;j++)

			{

				if(dp[i][j]==0)

				{

					f[i][j]=1;

					continue;

				}

				if(dp[i-1][j]==dp[i][j])

				{

					(f[i][j]=f[i-1][j])%=mod;

				}

				int p= meet[j][x[i-1]-'a'];

				if(dp[i-1][p-1]+1==dp[i][j])(f[i][j]+=f[i-1][p-1])%=mod;

			}

		}

		cout<<f[m][n]%mod<<endl;

	}

	return 0;

}

f[i][j]+=f[i−1][j]

f[i][j]+=ff[i][j]+=f[i−1][j]

f[i][j]+=f[i−1][j]

f[i][j]+=f[i−1][j]

f[i][j]+=f[i−1][j]

f[i][j]+=f[i−1][j]

f[i][j]+=f[i−1][j]

巴特西

HDU 5282：Senior's String

Senior's String

最新文章

热门文章