Substring and Subsequence -每天一把CF - 20201110
程序员文章站
2022-06-09 19:50:32
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
思路
题目大意:两个字符串,从第一个字符串中取子串(元素连续),从第二个字符串中取子序列(元素不要求连续),若子串和子序列一模一样就算一个有效对,问总共有多少有效对(只要有本来的索引不一致就可以认为是不同的有效对)。
思路:和最长公共子序列有点关系又有点不同,毕竟第一个序列要求的是子串。
先给出状态定义和状转公式
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