---

title: NOIp2016 子串

date: 2018-03-31 22:08:58

tags:

- DP

categories:

- 题解

- NOIp

- 2015

---

挺有意思的 DP

设 \(dp[i,j,k,l]\) 为字符串 A 的第 \(i\) 位匹配到了字符串 B 第 \(j\) 位，选出了 \(k\) 个子串，\(l\) 为 \(0\) \(A_i\) 就不选。

然后转移就是比较明显的

\[ \begin{cases} dp[i,j,k,0] = dp[i-1,j,k,1] + dp[i-1,j,k,0] & anytime\\\ dp[i,j,k,1] = dp[i-1,j-1,k-1,1] + dp[i-1,j-1,k,1] + dp[i-1,j-1,k-1,0] & A_i=B_j \end{cases} \]

蛤？听说你想要开 \(1000∗200∗200∗2\) 的数组？

太 naive 辣！

可以发现，每次转移都只跟 \(dp[i-1]\) 有关系，所以只要使用滚动膜法数组就行啦！

#include 
    
     #include 
     
      const int max_n = 1000 + 5;const int max_m = 200 + 5;const int mod = 1e9 + 7;int N, M, K;int Dp[2][max_m][max_m][2];char A[max_n], B[max_m];int main(){    scanf("%d %d %d", &N, &M, &K);    scanf("%s", &A[1]);    scanf("%s", &B[1]);    Dp[0][0][0][0] = 1;    for(int i = 1; i <= N; ++i)    {        int o = i & 1;        Dp[o][0][0][0] = 1;        for(int j = 1; j <= std::min(i, M); ++j)        {            for(int k = 1; k <= std::min(j, K); ++k)            {                int t = o ^ 1;                Dp[o][j][k][0] = (Dp[t][j][k][0] + Dp[t][j][k][1]) % mod;                if(A[i] == B[j]) Dp[o][j][k][1] = (((Dp[t][j - 1][k - 1][0] + Dp[t][j - 1][k - 1][1]) % mod ) + Dp[t][j - 1][k][1]) % mod;                else Dp[o][j][k][1] = 0;            }        }    }    printf("%d\n", (Dp[N & 1][M][K][0] + Dp[N & 1][M][K][1]) % mod);    return 0;}