欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Substring and Subsequence -每天一把CF - 20201110

程序员文章站 2022-03-27 21:52:47
2020-11-10dp163A 1800题目原题链接:https://codeforces.com/problemset/problem/163/A思路题目大意:两个字符串,从第一个字符串中取子串(元素连续),从第二个字符串中取子序列(元素不要求连续),若子串和子序列一模一样就算一个有效对,问总共有多少有效对(只要有本来的索引不一致就可以认为是不同的有效对)。思路:和最长公共子序列有点关系又有点不同,毕竟第一个序列要求的是子串。先给出状态定义和状转公式dp[i][j]表示以a[i]....

2020-11-10

dp

163A 1800

题目

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

Substring and Subsequence -每天一把CF - 20201110

思路

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

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

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

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