【uoj149】 NOIP2015

题意

　　给出两个字符串A、B，问从A中取出k个互不重叠的子串按顺序组成B的方案数。

Solution

　　一看这种题目就是字符串dp，字符串dp的话套路都差不多。一开始我直接无脑${f[k][i][j]}$，表示从A串前缀${i}$中取出${k}$个子串组成B串前缀${j}$的方案数，但是这样做的话转移过来的状态有点多，不太好讨论。。于是我又开了一个${g}$数组来记录一种状态。

　　于是，${g[k][i][j]}$表示从A串前缀${i}$中取出${k}$个子串组成B串前缀${j}$的方案数，并且最后一个子串的最后一个字母是${A[i]}$。${f[k][i][j]}$表示从A串前缀${i}$中取出${k}$个子串组成B串前缀${j}$的方案数，并且最后一个子串的最后一个字母不是${A[i]}$。

　　那么转移就分两种情况：

　　1.当${a[i]=b[i]}$，那么：${g[k][i][j]=f[k-1][i-1][j-1]+g[k][i-1][j-1]+g[k-1][i-1][j-1]}$。

　　2.无论${a[i]}$是否等于${b[i]}$，${f[k][i][j]=f[k][i-1][j]+g[k][i-1][j]}$。

　　很好理解吧。然后发现第一维的${k}$只会与前面的${k-1}$有关，为了节省空间我就把它滚动了。

细节

　　滚动数组记得每次开始时清空。

代码

// uoj150

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define MOD 1000000007

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=1010;

LL f[2][maxn][210],g[2][maxn][210];

char a[maxn],b[maxn];

int n,m,K;

int main() {

	scanf("%d%d%d",&n,&m,&K);

	scanf("%s",a+1);

	scanf("%s",b+1);

	int x=0;

	for (int k=0;k<=K;k++)

		for (int i=0;i<=n;i++) f[0][i][0]=f[1][i][0]=1;

	for (int k=1;k<=K;k++) {

		x^=1;

		memset(f[x],0,sizeof(f[x]));memset(g[x],0,sizeof(g[x]));

		for (int i=k;i<=n;i++)

			for (int j=k;j<=min(i,m);j++) {

				if (a[i]==b[j])

					g[x][i][j]=(f[x^1][i-1][j-1]+g[x][i-1][j-1]+g[x^1][i-1][j-1])%MOD;

				f[x][i][j]=(f[x][i-1][j]+g[x][i-1][j])%MOD;

			}

	}

	printf("%lld",(f[x][n][m]+g[x][n][m])%MOD);

	return 0;

}

巴特西

【uoj149】 NOIP2015—子串

题意

Solution

细节

代码

最新文章

热门文章