南桥做网站,营销类网站建设,装修公司手机网站模板,网店代运营合同模板正题
题目链接:https://www.ybtoj.com.cn/contest/66/problem/3 题目大意
给出两个字符串A,BA,BA,B#xff0c;求它们的最长公共子序列。 解题思路
先考虑朴素的dpdpdp#xff0c;设fi,jf_{i,j}fi,j表示到AAA的第iii个#xff0c;BBB的第jjj个时候的最长公共子序列长度…正题
题目链接:https://www.ybtoj.com.cn/contest/66/problem/3 题目大意
给出两个字符串A,BA,BA,B求它们的最长公共子序列。 解题思路
先考虑朴素的dpdpdp设fi,jf_{i,j}fi,j表示到AAA的第iii个BBB的第jjj个时候的最长公共子序列长度。
发现这样的dpdpdp由于A的长度很大B的长度很小所以导致dpdpdp里的数值很小转移却十分冗长。发现还有一种最优的状态表示法当匹配到BBB的相同位置且当且公共长度相同时显然在AAA的位置越前越好。那么可以设fi,jf_{i,j}fi,j表示匹配到BBB的第iii个时目前公共长度为jjj的在AAA中最前的位置。
时间复杂度O(26nm2)O(26nm^2)O(26nm2) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610,M1100;
int n,m,last[26],nxt[N][26],f[M][M];
char a[N],b[M];
int main()
{freopen(lcs.in,r,stdin);freopen(lcs.out,w,stdout);scanf(%s,a1);nstrlen(a1);scanf(%s,b1);mstrlen(b1);for(int in;i0;i--){for(int j0;j26;j)nxt[i][j]last[j];if(i)last[a[i]-a]i;}memset(f,0x3f,sizeof(f));f[0][0]0;for(int i1;im;i){for(int j0;ji;j){if(jf[i-1][j-1]nnxt[f[i-1][j-1]][b[i]-a])f[i][j]min(f[i][j],nxt[f[i-1][j-1]][b[i]-a]);f[i][j]min(f[i][j],f[i-1][j]);}}for(int im;i0;i--)if(f[m][i]2147483647/3)return printf(%d\n,i);return 0;
}
