日常训练2025-1-12

P2679 [NOIP2015 提高组] 子串

普及+/提高

https://www.luogu.com.cn/problem/P2679

思路

https://www.luogu.com.cn/article/k0zkdin9

评述

做DP时可以把能想到的有用的状态都定义出来，后序在把不需要的，或者可以根据其他状态推出来的状态删除，逐渐优化。

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 1000000007
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n, m, k;
	std::cin >> n >> m >> k;

	std::string a, b;
	std::cin >> a >> b;

	a = ' ' + a;
	b = ' ' + b;

	std::vector dp(m+1, std::vector<std::vector<int>>(k+1, std::vector<int>(2)));
	std::vector ndp(m+1, std::vector<std::vector<int>>(k+1, std::vector<int>(2)));	

	dp[0][0][0] = 1;
	ndp[0][0][0] = 1;

	for (int i = 1; i <= n; i++){
		ndp = dp;
		for (int j = 1; j <= m; j++){
			for (int p = 1; p <= k; p++){
				if (a[i] == b[j]){
					dp[j][p][1] = (ndp[j-1][p][1] + ndp[j-1][p-1][1]) % MOD + ndp[j-1][p-1][0] % MOD;
					dp[j][p][1] %= MOD;
					dp[j][p][0] = (ndp[j][p][1] + ndp[j][p][0]) % MOD;
				}else{
					dp[j][p][1] = 0;
					dp[j][p][0] = (ndp[j][p][1] + ndp[j][p][0]) % MOD;
				}
			}
		}
	}

	std::cout << (dp[m][k][0] + dp[m][k][1]) % MOD << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}