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

叼毛兽蒟蒻 · 2020-10-20 13:29:15 · 题解

本蒟蒻第一次来发题解啦

注释已在代码中

上代码！！！！！！

我知道这是你们最爱的

#include<bits/stdc++.h>//神奇万能头
using namespace std;

#define maxn 5000//define用于定义常量，const也行
#define md 100000000

int n,m;
char a[maxn+5]= {0},b[maxn+5]= {0};//char数组
int f[3][maxn+5]= {0},g[3][maxn+5]= {0};

void readin() {
    for(int i=1;; i++) {//for循环，不多解释
        bool flag=true;//bool函数，对或错
        while(~scanf("%c",&a[i])) {//输入
            if(a[i]=='.') {
                flag=false;
                break;//跳出可爱的循环
            }
            if(isalpha(a[i])) break;
        }
        if(!flag) {//if条件句，！是非的意思
            n=i;
            n--;
            break;

    }
    for(int i=1;; i++) {
        bool flag=true;
        while(~scanf("%c",&b[i])) {
            if(b[i]=='.') {
                flag=false;
                break;
            }
            if(isalpha(b[i])) break;
        }
        if(!flag) {
            m=i;
            m--;
            break;
        }
    }
    for(int i=0;i<=m;i++) g[0][i]=1;g[1][0]=1;
}

void dp() {
    for (int i=1; i<=n; i++) {
        int x=i%2;//%，取余
        int y=(i-1)%2;
        for (int j=1; j<=m; j++) {
            if (a[i]==b[j]) {
                f[x][j]=f[y][j-1]+1;
                g[x][j]=g[y][j-1];
                if (f[x][j]==f[y][j]) g[x][j]=(g[x][j]+g[y][j])%md;
                if (f[x][j]==f[x][j-1]) g[x][j]=(g[x][j]+g[x][j-1])%md;
            } else {
                f[x][j]=max(f[x][j-1],f[y][j]);
                g[x][j]=0;
                if (f[x][j]==f[y][j-1]) g[x][j]=(g[x][j]-g[y][j-1])%md;
                if (f[x][j]==f[y][j]) g[x][j]=(g[x][j]+g[y][j])%md;
                if (f[x][j]==f[x][j-1]) g[x][j]=(g[x][j]+g[x][j-1])%md;
            }
        }
    }
}

int main() {
    readin();
    dp();
    printf("%d\n%d\n",f[n%2][m],(g[n%2][m]%md+md)%md);//愉快的输出

    return 0;//好习惯要养成，妙呀
}

溜了溜了。。。。。。