题解 P3856 【[TJOI2008]公共子串】

Jμdge · 2019-03-28 12:37:09 · 题解

白痴了，只会做 SB 题了，这题居然没想出来...

noteskey

考虑一下数据范围里说字符串长度只有 100 ，然后是三个字符串，那么三层的 dp 也就是 n^3

然后枚举字符转移套个常数 26

很稳，代码也很短...

code

//by Judge
#include<cstdio>
#include<cstring>
#include<iostream>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define ll long long
using namespace std;
const int M=103;
typedef int arr[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline void reads(string& s){ char c=getchar();
    for(;!isalpha(c);c=getchar()); s=" ";
    for(;isalpha(c);c=getchar()) s+=c;
} int n1,n2,n3,las[4]['z'+1];
ll f[M][M][M]; string s1,s2,s3;
int main(){
    reads(s1),reads(s2),reads(s3); //毒瘤的字符串读优
    n1=s1.length()-1;
    n2=s2.length()-1;
    n3=s3.length()-1;
    fp(i,1,n1){ las[1][s1[i]]=i,memset(las[2],0,sizeof las[2]);
        fp(j,1,n2){ las[2][s2[j]]=j,memset(las[3],0,sizeof las[3]);
            fp(k,1,n3){ las[3][s3[k]]=k; 
                fp(x,'a','z'){ int ii=las[1][x],jj=las[2][x],kk=las[3][x];
                    if(ii&&jj&&kk) f[i][j][k]+=f[ii-1][jj-1][kk-1]+1;
                }
            }
        }
    }
    return !printf("%lld\n",f[n1][n2][n3]);
}