almost 4 years ago
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define maxn 5001

#define Mod 100000000

using namespace std;
int dp[2][maxn]={0},sum[2][maxn]={0}; 
char a[maxn],b[maxn];
int n,m;
void add(int &x,int y)
{
    x=(x+y)%Mod;
}
void dec(int &x,int y)
{
    x=(x-y+Mod)%Mod;
}
int main()
{    
    scanf("%s%s",a+1,b+1);
    int i,j,now;
    n=strlen(a+1)-1;m=strlen(b+1)-1;
    for (i=0;i<=m;i++) sum[0][i]=1;
    for (i=1;i<=n;i++)
    {now=i&1;
    memset(dp[now],0,sizeof(dp[now]));
    memset(sum[now],0,sizeof(sum[now]));
    sum[now][0]=1;
    for (j=1;j<=m;j++)
    {    //一开始自己yy的。注意最后一步减去是重点。
        if (a[i]==b[j]) dp[now][j]=dp[now^1][j-1]+1;
        dp[now][j]=max(dp[now^1][j],max(dp[now][j-1],dp[now][j]));
        if (a[i]==b[j]&&dp[now][j]==dp[now^1][j-1]+1) add(sum[now][j],sum[now^1][j-1]);
        if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
        if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);
        if (dp[now][j]==dp[now][j-1]&&dp[now^1][j-1]==dp[now^1][j]&&dp[now^1][j]==dp[now][j-1])dec(sum[now][j],sum[now^1][j-1]);
        //如果a[i]!=b[j]dp[now][j-1]==dp[now^1][j],则说明他们==dp[now^1][j-1]
        //   这样的话就会多算一遍,必须减去【MARK!! 
    /* WYL版。简单直白。 
        if (a[i]==b[j]) 
        {dp[now][j]=dp[now^1][j-1]+1;
        dp[now][j]=max(dp[now^1][j],max(dp[now][j-1],dp[now][j]));
        if (dp[now][j]==dp[now^1][j-1]+1) add(sum[now][j],sum[now^1][j-1]);
        if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
        if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);}
        else
        {
            dp[now][j]=max(dp[now^1][j],dp[now][j-1]);
            if (dp[now][j]==dp[now^1][j]) add(sum[now][j],sum[now^1][j]);
            if (dp[now][j]==dp[now][j-1]) add(sum[now][j],sum[now][j-1]);           
            if (dp[now^1][j]==dp[now][j-1]&&dp[now^1][j-1]==dp[now][j-1])
            //if (dp[now][j]==dp[now^1][j-1])也是满足的,因为不可能dp[now][j-1],dp[now^1][j]<dp[now^1][j-1] 
             dec(sum[now][j],sum[now^1][j-1]);
        }*/
    }}
    printf("%d\n%d\n",dp[n&1][m],sum[n&1][m]);
}
← 报道~ 【bzoj1977】次小生成树 →
 
comments powered by Disqus