【Codevs 4560】[NOIP2015] 子串

题目传送门:http://codevs.cn/problem/4560/

就是一个很简单的DP加一个滚动数组的优化
然而为什么纸张的我去年连这是个DP都看不出来 QAQ

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

const int MOD = 1000000007; 

int f[2][209][209][2],w,p,n,m,K;
char s1[1009],s2[1009];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read(); m = read(); K = read();
	scanf("%s%s",s1+1,s2+1);
	w = 1; f[p][0][0][0] = 1;
	
	for (int t=1;t<=n;t++,w^=1,p^=1) {
		memset(f[w],0,sizeof(f[w]));
		for (int i=0;i<=m;i++) {
			for (int k=0;k<=K;k++) {
				if (f[p][i][k][0]) {
					(f[w][i][k][0] += f[p][i][k][0]) %= MOD;
					if (s1[t] == s2[i+1]) {
						(f[w][i+1][k+1][1] += f[p][i][k][0]) %= MOD;
					}
				}
				if (f[p][i][k][1]) {
					(f[w][i][k][0] += f[p][i][k][1]) %= MOD;
					if (s1[t] == s2[i+1]) {
						(f[w][i+1][k][1] += f[p][i][k][1]) %= MOD;
						(f[w][i+1][k+1][1] += f[p][i][k][1]) %= MOD;
					}
				}
			}
		}
	}
	printf("%d\n",(f[p][m][K][0]+f[p][m][K][1])%MOD);
	return 0;
}

One thought to “【Codevs 4560】[NOIP2015] 子串”

Leave a Reply to 2tj Cancel reply

Your email address will not be published. Required fields are marked *