题解：P2679 [NOIP 2015 提高组] 子串

P2679 [NOIP 2015 提高组] 子串

题目

给出两个字符串

A

和

B

，在

A

中取出

k

个互不重叠的子串，使得这些子串按顺序拼接在一起时等于

B

，求方案数。

状态

一看是神秘的方案题，很容易想到 dp。为了方便，可以用数组

a

和

b

存下

A

和

B

的 ASCII 码方便转移和优化复杂度，这样做是正确的原因是只关注两个字符是否相等而不是其他性质。

我们可以令

f_{i,j,t}

表示此时枚举数组

a

前

i-1

都已算完，到第

i

项，枚举数组

b

前

j-1

项都已算完，到第

j

项，还可以取出

t

个子串时的状态。

这是常规的设计状态的思路，但我们很快发现，这样设计时不好辨别选取该项时是不是和上一个选的是同一个子串，于是我们便要增加维度。

令

f_{i,j,t,0/1}

，其中

i

，

j

，

t

意思同上，

0

表示不取数组

a

中的第

i

项，

1

表示取。

容易发现，该状态可以在转移的时候进行判断，于是就可以开始状态转移。

转移

转移的时候进行分类讨论。

当 $i > j$ 时， $f_{i,j,t,0} = f_{i,j,t,1} = 0$ 。
当 $a_{i} \ne b_{j}$ 时， $i$ 不能匹配 $j$ ，只能从前面的状态进行转移，即：

\Large{f_{i,j,t,0} = f_{i-1,j,t,0} + f_{i-1,j,t,1}}

当 $a_{i} = b_{j}$ 时，可以用 $a_{i}$ 匹配 $b_{j}$ ，此时要么 $i-1$ 的选了可以成为一个子串，要么新开一个子串，即：

\Large{f_{i,j,t,0} = f_{i-1,j,t,0} + f_{i-1,j,t,1}} \\ \Large{f_{i,j,t,1} = f_{i-1,j-1,t,1} + f_{i-1,j-1,t-1,0} + f_{i-1,j-1,t-1,1}}

Code

CPP

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e3+1 , M = 201 , inf = 1e9+7;

int n , m , k , a[N] , b[M];

LL f[N][M][M][2];

string in;

int main()
{
	ios::sync_with_stdio (false);
	
	cin >> n >> m >> k;
	
	cin >> in;
	
	for(int i = 1 ; i <= n ; i ++)
	{
		a[i] = in.at(i-1) - 'a' + 1;
	}
	
	cin >> in;
	
	for(int i = 1 ; i <= m ; i ++)
	{
		b[i] = in.at(i-1) - 'a' + 1;
	}
	
	f[0][0][0][0] = 1;
	
	for(int i = 1 ; i <= n ; i ++)
	{
		f[i][0][0][0] = 1;
		for(int j = 1 ; j <= m && j <= i ; j ++)
		{
			for(int t = 1 ; t <= k ; t ++)
			{
				f[i][j][t][0] = (f[i-1][j][t][0] + f[i-1][j][t][1]) % inf;
				if(a[i] == b[j])
				{
					f[i][j][t][1] = (f[i-1][j-1][t][1] + f[i-1][j-1][t-1][0] + f[i-1][j-1][t-1][1]) % inf;
				}			
			}
		}
	}
	
	cout << (f[n][m][k][0] + f[n][m][k][1]) % inf << "\n";
	
	return 0;
}

然而，只有

10

分。

这么大的空间

1000 \times 200 \times 200 \times 2 = 8 \times 10^7

谁不迷糊。

可以发现每个状态的

i

只依赖于

i-1

，于是可以滚动数组优化。

用取模运算或交替覆盖方式访问滚动数组。这里取模

2

可以近似看作位运算 &。

AC Code

CPP

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e3+1 , M = 201 , inf = 1e9+7;

int n , m , k , a[N] , b[M];

LL f[2][M][M][2];

string in;

int main()
{
	ios::sync_with_stdio (false);
	
	cin >> n >> m >> k;
	
	cin >> in;
	
	for(int i = 1 ; i <= n ; i ++)
	{
		a[i] = in.at(i-1) - 'a' + 1;
	}
	
	cin >> in;
	
	for(int i = 1 ; i <= m ; i ++)
	{
		b[i] = in.at(i-1) - 'a' + 1;
	}
	
	f[0][0][0][0] = f[1][0][0][0] = 1;
	
	for(int i = 1 ; i <= n ; i ++)
	{
		for(int j = 1 ; j <= m && j <= i ; j ++)
		{
			for(int t = 1 ; t <= k ; t ++)
			{
				f[i&1][j][t][0] = (f[(i-1)&1][j][t][0] + f[(i-1)&1][j][t][1]) % inf;
				if(a[i] == b[j])
				{
					f[i&1][j][t][1] = (f[(i-1)&1][j-1][t][1] + f[(i-1)&1][j-1][t-1][0] + f[(i-1)&1][j-1][t-1][1]) % inf;
				}
				else f[i&1][j][t][1] = 0;
        // 这里注意，因为把数组复用了，转移不了的要清零。
			}
		}
	}
	
	cout << (f[n&1][m][k][0] + f[n&1][m][k][1]) % inf << "\n";
	
	return 0;
}

题解：P2679 [NOIP 2015 提高组] 子串

文章操作

P2679 [NOIP 2015 提高组] 子串

题目

状态

转移

Code

AC Code

相关推荐

评论

题解：P2679 [NOIP 2015 提高组] 子串