Substring and Subsequence -每天一把CF - 20201110

2020-11-10

dp

163A 1800

题目

原题链接：https://codeforces.com/problemset/problem/163/A

思路

题目大意：两个字符串，从第一个字符串中取子串（元素连续），从第二个字符串中取子序列（元素不要求连续），若子串和子序列一模一样就算一个有效对，问总共有多少有效对（只要有本来的索引不一致就可以认为是不同的有效对）。

思路：和最长公共子序列有点关系又有点不同，毕竟第一个序列要求的是子串。

先给出状态定义和状转公式

dp[i][j]表示以a[i]结尾的子串和b[1-j]中子序列符合题意的匹配对的数量
    
if (a[i] == b[j])dp[i][j] = (dp[i - 1][j - 1] + 1) % mod;
dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;

首先看a[i]!=b[j]的时候，那只能把状态向前推一个，那就是dp[i-1][j]和dp[i][j-1]两种情况了，但这里与dp[i-1][j]是没有关系的，因为你的a[i]根本找不到匹配的对象，因为我们实际上都是在上一个状态的基础上在去加上a[i]或b[j]组成新的匹配对象的，前者直接放弃。而后者是有可能的。

再看当a[i]==b[j]的时候 明显再在i-1，j-1的基础上再加上a[i]与b[j]这一种匹配就好了。

另一道题一个点卡了一天还没搞懂 我吐了。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <string>
using namespace std;

#define mes0(c) memset((c),0,sizeof(c))
#define fsios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(n) for(int i=1;i<=(n);i++)
#define inp(a, n) for (int i = 1; i <= (n); i++) cin >> a[i];
#define ll long long
#define fi first
#define se second

const ll MAX = 5e3 + 5;
const ll ifi = 1e17 + 5;
const ll mod = 1e9 + 7;

int n, ans;
ll dp[MAX][MAX];
char a[MAX], b[MAX];
/*
dp[i][j]表示a[1-i]和b[1-j]符合题意的匹配对的数量
a要求子串
b要求子序列
*/

int main() {
	fsios;

	while (cin >> a + 1 >> b + 1) {

		int len1 = strlen(a + 1), len2 = strlen(b + 1);
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (a[i] == b[j])dp[i][j] = (dp[i - 1][j - 1] + 1) % mod;
				dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
			}
			ans = (ans + dp[i][len2]) % mod;
		}

		cout << ans << endl;
		mes0(dp); mes0(a); mes0(b);
		ans = 0;

	}
	return 0;
}

本文地址：https://blog.csdn.net/weixin_45761327/article/details/109610185