星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

P2516 [HAOI2010] 最长公共子序列

posted on 2017-12-25 20:36:05 | under 题解 |

这是我们很久以前的训练题。

一开始我看到题目名字的时候,以为像某些命名为线段树/树状数组/单旋等某些省选题一样根本不是用这个东西写题,但看着看着就发现第一问神TM就是裸LCS······

f[i][j]定义是LCS,ans[i][j]指a前i字母b前j字母的方案数。

然后第二问主要取决于f[i-1][j-1],f[i][j-1],f[i=1][j=1]与f[i][j]的相等性。

当f[i][j]==f[i-1][j]/f[i][j-1]的时候,直接加上对应的ans就可以了;

当f[i][j]=f[i-1][j-1]+1的时候,ans也加;

当f[i][j]==f[i-1][j-1]时则要把对应的ans[i-1][j-1]的方案减去。

然后不要忘了取模、字符串长度要减1。

代码难度不大,重在脑补理解。

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #define f(i,a,b) for(register int i=a;i<=b;++i)
    int f[2][5010],ans[2][5010],n,m;
    const int mod=1e8;
    char a[5010],b[5010];
    int now=1,pre;
    int main()
    {
    //    freopen("lcs.in","r",stdin);
    //    freopen("lcs.out","w",stdout);
        scanf("%s%s",a+1,b+1);
        n=strlen(a+1)-1,m=strlen(b+1)-1;
        ans[1][0]=1;f(i,0,m)ans[0][i]=1;
        f(i,1,n)
        {
         f(j,1,m)
         {
             f[now][j]=std::max(f[pre][j],f[now][j-1]);
             ans[now][j]=0;
             if(a[i]==b[j])
            {
                f[now][j]=std::max(f[now][j],f[pre][j-1]+1);
                if(f[now][j]==f[pre][j-1]+1)ans[now][j]+=ans[pre][j-1];    
            }
             if(f[pre][j]==f[now][j])ans[now][j]+=ans[pre][j];
             if(f[now][j-1]==f[now][j])ans[now][j]+=ans[now][j-1];
             if(f[pre][j-1]==f[now][j])ans[now][j]-=ans[pre][j-1];
             ans[now][j]%=mod;
         }now=pre,pre^=1;
        }
        printf("%d\n%d\n",f[pre][m],(ans[pre][m]+mod)%mod);
}