您现在的位置是：主页 > news > 网站建设公司做销售前景好不好/外链工具xg
网站建设公司做销售前景好不好/外链工具xg
admin2025/4/30 18:00:01【news】
简介网站建设公司做销售前景好不好,外链工具xg,wordpress网盘搜索引擎插件,图片制作gifDescription 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X“x0，x1，…，xm-1”，序列Y“y0&#…
网站建设公司做销售前景好不好,外链工具xg,wordpress网盘搜索引擎插件,图片制作gifDescription 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X“x0，x1，…，xm-1”，序列Y“y0&#…
Description
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。
Input
第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。
第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。
Output
第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对100,000,000求余即可。
Sample Input
ABCBDAB.
BACBBD.
BACBBD.
Sample Output
4
7
题解
1. 当 s1==s2[j] 时
若 dp[i][j-1]>dp[i-1][j], 那么dp[i][j]=dp[i][j-1], g[i][j]=g[i][j-1]; 这很容易理解，但接下来就难了
若 dp[i][j-1]==dp[i-1][j] 那么dp[i][j]=dp[i-1][j] 也可以=dp[i][j-1], g[i][j]=g[i-1][j]+g[i][j-1],但如果同时dp[i][j]==dp[i-1][j-1], 那么g[i][j]-=g[i-1][j-1], 因为g[i-1][j-1] 被重复计算了一遍
7
题解
我们知道如何求最长公共子序列，即设一个数组 dp[j], 表示扫描到 s1 和 s2[j] 时的最长公共子序列长度。
此题还需要求出方案数，我们就利用 dp[j], 设一个记录每一个 dp[j] 的方案数的数组 g[j]
1. 当 s1==s2[j] 时
我们就 dp[j]=dp[i-1][j-1], g[j]=g[i-1][j-1], 此时 dp[i-1][j] 和 dp[j-1] 都不会大于 dp[j], 但可能与 dp[i][j] 相等，哪一个与之相等，g[i][j] 就 += 哪一个的 g
2. 若 s1[i]!=s2[j]
情况比较复杂。若 dp[i][j-1]>dp[i-1][j], 那么dp[i][j]=dp[i][j-1], g[i][j]=g[i][j-1]; 这很容易理解，但接下来就难了
若 dp[i][j-1]==dp[i-1][j] 那么dp[i][j]=dp[i-1][j] 也可以=dp[i][j-1], g[i][j]=g[i-1][j]+g[i][j-1],但如果同时dp[i][j]==dp[i-1][j-1], 那么g[i][j]-=g[i-1][j-1], 因为g[i-1][j-1] 被重复计算了一遍
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=5010;
const int mod=100000000;
char a[maxn],b[maxn];
int dp[3][maxn];
int g[3][maxn];
int main(){scanf("%s",a+1);scanf("%s",b+1);int len1=strlen(a+1)-1;int len2=strlen(b+1)-1;g[1][0]=1;for(int i=0;i<=len2;i++)g[0][i]=1;int pre=1,now=0;for(int i=1;i<=len1;i++){swap(now,pre);for(int j=1;j<=len2;j++){if(a[i]==b[j]){dp[now][j]=dp[pre][j-1]+1;g[now][j]=g[pre][j-1];if(dp[now][j]==dp[pre][j])g[now][j]=(g[now][j]+g[pre][j])%mod;if(dp[now][j]==dp[now][j-1])g[now][j]=(g[now][j]+g[now][j-1])%mod;}else{dp[now][j]=max(dp[pre][j],dp[now][j-1]);g[now][j]=0;if(dp[now][j]==dp[pre][j])g[now][j]=(g[now][j]+g[pre][j])%mod;if(dp[now][j]==dp[now][j-1])g[now][j]=(g[now][j]+g[now][j-1])%mod;if(dp[now][j]==dp[pre][j-1])g[now][j]=(g[now][j]-g[pre][j-1])%mod;}}}printf("%d\n",dp[now][len2]);printf("%d\n",(g[now][len2]+mod)%mod);return 0;
}
