首页 > 其他 > 详细

题解【洛谷P2516】[HAOI2010]最长公共子序列

时间:2020-03-11 21:42:43      阅读:84      评论:0      收藏:0      [点我收藏+]

题面

经典的 LCS 求方案数。

第一问很简单,直接 \(O(n^2)\) 求出序列 LCS 长度即可。

对于第二问,直接在转移的时候分类讨论一下,最后处理重复计算的情况就可以了。

注意这一题卡空间,需要开滚动数组优化空间。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <LL, LL> PII;
typedef pair <LL, PII> PIII;

const LL INF = 0x3f3f3f3f, N = 5003, mod = 100000000;

LL n, m;
LL dp[2][N], g[2][N];
char s[N], t[N];

int main()
{
    //File("");
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1) - 1, m = strlen(t + 1) - 1;
    g[1][0] = 1;
    for (LL i = 0; i <= m; i+=1) g[0][i] = 1;
    for (LL i = 1; i <= n; i+=1)
        for (LL j = 1; j <= m; j+=1)
        {
            dp[i & 1][j] = dp[i - 1 & 1][j], g[i & 1][j] = g[i - 1 & 1][j] % mod;
            if (dp[i & 1][j] == dp[i & 1][j - 1]) (g[i & 1][j] += g[i & 1][j - 1]) %= mod;
            else if (dp[i & 1][j - 1] > dp[i & 1][j]) dp[i & 1][j] = dp[i & 1][j - 1], g[i & 1][j] = g[i & 1][j - 1] % mod;
            if (s[i] == t[j])
            {
                if (dp[i - 1 & 1][j - 1] + 1 > dp[i & 1][j])
                    dp[i & 1][j] = dp[i - 1 & 1][j - 1] + 1, g[i & 1][j] = g[i - 1 & 1][j - 1] % mod;
                else if (dp[i - 1 & 1][j - 1] + 1 == dp[i & 1][j]) (g[i & 1][j] += g[i - 1 & 1][j - 1]) %= mod;
            }
            else if (dp[i & 1][j - 1] == dp[i - 1 & 1][j] && dp[i - 1 & 1][j] == dp[i - 1 & 1][j - 1]) 
                g[i & 1][j] -= g[i - 1 & 1][j - 1]; //重复转移的情况
        }
    printf("%lld\n%lld\n", dp[n & 1][m], (g[n & 1][m] % mod + mod) % mod);
    return 0;
}

题解【洛谷P2516】[HAOI2010]最长公共子序列

原文:https://www.cnblogs.com/xsl19/p/12465302.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!