[ HAOI 2010 ] 最长公共子序列

\(\\\)

\(Description\)

求两个长度\(\le5000\)的大写字母串的\(LCS\)长度及个数，定义两\(LCS\)中某一字符在两序列出现位置有一处不同就视为不同。

\(\\\)

\(Solution\)

既然是基于下标不同的LCS那不就可以随便乱搞

求\(LCS\)的时候定义\(f[i][j]\)表示第一个序列处理到第\(i\)个位置，第二个序列处理到第\(j\)个位置时\(LCS\)的长度，类似的定义\(g[i][j]\)为该情况下\(LCS\)的个数。
大力\(DP\)就好，\(f[i][j]\)照常转移，\(g[i][j]\)需要根据转移的情况讨论：
- 首先若最后得到的答案转移自\(f[i-1][j]\)或\(f[i][j-1]\)，那么要加上对应的方案数
- 若发现\(f[i-1][j-1]=f[i][j]\)，证明新加的两个字符都没有用到，而累加了两次，所以要减掉
- 最后若转移还有\(s1[i]=s2[i]\)的情况，方案数也要对应加上\(f[i-1][j-1]\)，注意到这一情况与上一情况必定是不同的，所以无需考虑冲突的部分。
直接开存不下，滚动数组。

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define N 5010

#define R register

#define gc getchar

#define mod 100000000

using namespace std;

char s1[N],s2[N];

int tot1,tot2,f[2][N],g[2][N];

int main(){

  char c=gc();

  while(!isupper(c)) c=gc();

  s1[tot1=1]=c;

  while(isupper(c=gc())) s1[++tot1]=c;

  while(!isupper(c)) c=gc();

  s2[tot2=1]=c;

  while(isupper(c=gc())) s2[++tot2]=c;

  g[1][0]=1;

  for(R int i=0;i<=tot2;++i) g[0][i]=1;

  for(R int i=1,now;i<=tot1;++i){

    now=i&1;

    for(R int j=1;j<=tot2;++j){

      g[now][j]=0;

      f[now][j]=max(f[now^1][j],f[now][j-1]);

      if(s1[i]==s2[j]) f[now][j]=max(f[now][j],f[now^1][j-1]+1);

      if(s1[i]==s2[j]) (g[now][j]+=g[now^1][j-1])%=mod;

      if(f[now^1][j]==f[now][j]) (g[now][j]+=g[now^1][j])%=mod;

      if(f[now][j-1]==f[now][j]) (g[now][j]+=g[now][j-1])%=mod;

      if(f[now^1][j-1]==f[now][j]) (g[now][j]+=mod-g[now^1][j-1])%=mod;

    }

  }

  printf("%d\n%d",f[tot1&1][tot2],g[tot1&1][tot2]);

  return 0;

}

巴特西

[ HAOI 2010 ] 最长公共子序列

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章