欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[NOIP2015] 子串

程序员文章站 2024-03-20 13:08:04
...

[NOIP2015] 子串

题目大意:给出\(a,b\)两个串,可将\(a\)串划分为任意子串,子串按照在\(a\)中出现的次序组合为串\(c\),求有多少\(c\)\(b\)完全相同

这样子来DP

\(f[i][j][k]\)\(a\)串的前\(i\)个匹配\(b\)串的前\(j\)个,用了\(k\)次,且\(a\)串的第\(i\)一定被选中的方案总数.

\(s[i][j][k]\)\(a\)串的前\(i\)个匹配\(b\)串的前\(j\)个,用了\(k\)次,\(a\)串的第\(i\)不管选没选中的方案总数.

如果\(a_i=b_j\) \(f[i][j][k] = f[i - 1][j - 1][k] + s[i - 1][j - 1][k - 1]\),否则\(f[i][j][k] = 0\)

而无论何时,\(s[i][j][k]=f[i][j][k] + s[i - 1][j][k]\)

滚动数组优化

代码

#include <iostream>
#include <cstdio>

const int N = 1005;
const int Mod = 1000000007;

int n, m, h;
int f[3][205][205], s[3][205][205];
char a[N], b[N];

int main(){
    scanf("%d %d %d", &n, &m, &h);
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int qwq = 1;
    f[0][0][0] = s[0][0][0] = 1;//初始化
    for(int i = 1; i <= n; ++i, qwq ^= 1){
        f[qwq][0][0] = s[qwq][0][0] = 1;//初始化
        for(int j = 1; j <= m; ++j)
            for(int k = 1; k <= h; ++k){
                if(a[i] == b[j])
                    f[qwq][j][k] = (f[qwq ^ 1][j - 1][k] + s[qwq ^ 1][j - 1][k - 1]) % Mod;
                else 
                    f[qwq][j][k] = 0;
                    
                s[qwq][j][k] = (f[qwq][j][k] + s[qwq ^ 1][j][k]) % Mod; 
            }
        
    }
    printf("%d\n",s[qwq ^ 1][m][h]);
    return 0;
} 

按照题意选取最适合的状态来转移