首页 > 代码库 > tyvj2030 题解

tyvj2030 题解

2024-07-17 00:56:46   219人阅读

 

 

给出两个由数字和字母组成的非空字符串S，T，求：

1）S与T的最长公共子序列的长度。

2）S与T的本质不同的非空公共子序列的个数。

3）S与T的各种长度的本质不同的非空公共子序列的个数。

思考过程：考场上，果断只会第一问，但是听完题解后，发现事实上他们的思想和第一问是一致的。(此题解借鉴讲题解人）

首先考虑第二问，设dp(i,j)表示s串的前i位和t串的前j位，分两种情况讨论

若s[i]=s[j],则直接把这个字符接在后面，有接和不接两种则dp(i,j)=dp(i-1,j-1)*2,但是我们需要将此结果减去dp(u-1,v-1）其中uv是ij最近相同字符， 考虑dp[u-1][v-1]对应集合中的串x，记S[i]=c，则x,xc∈dp[u][v]，则x,xc∈dp[i-1][j-1]。串xc就会在dp[i][j]的集合中出现两遍。

若是s[i]!=s[j],则dp(i,j)=dp(i,j-1)+dp(i-1,j)-dp(i-1,j-1)

这样就解决了第二问，而第三问就是在第二问上加一维，k为长度，dp方程则是一模一样。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 string a,b; 7 int f[305][305]; 8 int g[305][305][305]; 9 int prea[305],preb[305];10 int ans;11 const int MOD=1048576;12 const int SIE = 0xFFFFF;13 int n,m;14 int ss;15 int main()16 {17 //    freopen("common5.in","r",stdin);18 //    freopen("common5.out","w",stdout);19     cin>>a;cin>>b;20     n=a.size();21     m=b.size();22     a=‘0‘+a;23     b=‘0‘+b;24     for(int i=1;i<=n;i++)25     {26         for(int j=1;j<=m;j++)27         {28             if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;29             f[i][j]=max(f[i][j],f[i-1][j]);30             f[i][j]=max(f[i][j],f[i][j-1]);31         }32     }33     printf("%d\n",f[n][m]);34     ss=f[n][m];35     for(int i=1;i<=n;i++)36     {37         int j=i-1;38         while(j>0 && a[j]!=a[i])j--;39         prea[i]=j;40     //    cout<<j;41     }42     for(int i=1;i<=m;i++)43     {44         int j=i-1;45         while(j>0 && b[j]!=b[i])j--;46         preb[i]=j;47         //cout<<j;48     }49     for(int i=0;i<=n;i++)50     {51         for(int j=0;j<=m;j++)52         {53             g[i][j][0]=1;54         }55     }56     for(int i=1;i<=n;i++)57     {58         for(int j=1;j<=m;j++)59         {60             if(a[i]==b[j])61             {62                 for(int k=1;k<=ss;k++)63                 {64                     g[i][j][k]=(g[i-1][j-1][k]+g[i-1][j-1][k-1])&SIE;65                 }66                 if(prea[i] && preb[j])67                 {68                     for(int k=1;k<=ss;k++)69                     {70                         g[i][j][k]=(g[i][j][k]-g[prea[i]-1][preb[j]-1][k-1])&SIE;71                     }72                 }73             }74             else75             {76                 for(int k=1;k<=ss;k++)77                 {78                     g[i][j][k]=(g[i-1][j][k]+g[i][j-1][k]-g[i-1][j-1][k])&SIE;79                     //cout<<i<<" "<<j<<" "<<k<<" "<<g[i][j][k]<<endl;80                 }81             }82         }83     }84     int sum=0;85     for(int i=1;i<=ss;i++)sum=(sum+g[n][m][i])%MOD;86     printf("%d\n",sum);87     for(int i=1;i<=ss;i++)printf("%d\n",g[n][m][i]);88     return 0;89 }
View Code

 


联系
我们