对AC自动机+DP题的一些汇总与一丝总结 (1)

(1)题意 : 输入n、m、k意思就是给你 m 个模式串，问你构建长度为 n 至少包含 k 个模式串的方案有多少种

分析：(HDU2825)

DP[i][j][k] 表示 DP[第几步][哪个节点结尾][当前选了哪些单词] = 方案数

 for(int i=0; i<=n; i++)
            for(int j=0; j<ac.Size; j++)
                for(int l=0; l<(1<<m); l++)
                    dp[i][j][l] = 0;
        dp[0][0][0] = 1;
        for(int i=0; i<n; i++){
            for(int j=0; j<ac.Size; j++){
                for(int l=0; l<(1<<m); l++){
                    if(dp[i][j][l] > 0){
                        for(int x=0; x<Letter; x++){ 
                            int newi = i+1;
                            int newj = ac.Node[j].Next[x];
                            int newl = (ac.Node[ newj ].id) | l; 
                            dp[newi][newj][newl] += dp[i][j][l];
                            dp[newi][newj][newl] %= MOD;
                        }
                    }
                }
            }
        }

(2)题意 : 给出 n 个模式串，最后给出一个主串，问你主串打乱重组的情况下，最多能够包含多少个模式串。（只有ATGC四总字符）(HDU3341)

(也就是说，给定了字母数量的限制去构造)

DP[A][T][G][C][Node]前四维表示ATGC数量，最后一维表示当前状态停留在节点 Node

即利用一个四维数组 Hash[11][11][11][11] ( 每一个字母最多就是 10 个，所以这样开数组 ) ，然后只需要统计主串各个种类字符的数量，

        for(int j=0; j<=ac.Size; j++)
            for(int i=0; i<=HashCnt; i++)
                dp[i][j] = -1;

    dp[0][0] = 0;

    for(int A=0; A<=num[0]; A++){
        for(int T=0; T<=num[1]; T++){
            for(int G=0; G<=num[2]; G++){
                for(int C=0; C<=num[3]; C++){
                    for(int i=0; i<ac.Size; i++){
                        int j = Hash[A][T][G][C];
                        if(dp[j][i] >= 0){
                            for(int k=0; k<4; k++){
                                if(k==0 && A == num[0]) continue;
                                if(k==1 && T == num[1]) continue;
                                if(k==2 && G == num[2]) continue;
                                if(k==3 && C == num[3]) continue;
                                int a, t, g, c;
                                a = (k==0), t = (k==1);
                                g = (k==2), c = (k==3);
                                dp[Hash[A+a][T+t][G+g][C+c]][ac.Node[i].Next[k]]
                                = max(dp[Hash[A+a][T+t][G+g][C+c]][ac.Node[i].Next[k]],
                                      dp[j][i] + ac.Node[ac.Node[i].Next[k]].cnt);
                            }
                        }
                    }
                }
            }
        }
    }

(3)题意 : 给出一个 n 行、m 列的方格图，现从图左上角(0, 0) 到右下角的 (n, m)走出一个字符串(规定只能往下或者往右走)，向右走代表' R ' 向下走则是代表 ' D ' 最后从左上角到右下角，不同的路线会走出不同的字符串，问你这些不同的字符串有多少个是包含了接下来给定的两个子串。（HDU 4758）

(用 (n+1) 个 ' D ' 和 (m+1)个 ' R ' 构造出长度为 (n+m+2) 的字符串，且包含给定的两个子串的方案数有多少个)

DP[i][j][k][l]代表在有 i 个 ' D '（即向下走了 i 步）、j 个 ' R '（向右走 j 步）、停留在 k 这个节点、包含子串情况 l 时的最大方案.

 for(int i=0; i<=n; i++)
        for(int j=0; j<=m; j++)
            for(int k=0; k<ac.Size; k++)
                for(int l=0; l<4; l++)
                    dp[i][j][k][l] = 0;

    dp[0][0][0][0] = 1;

    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            for(int k=0; k<ac.Size; k++){
                for(int l=0; l<4; l++){
                    if(dp[i][j][k][l] > 0){
                        int Node1 = ac.Node[k].Next[0];
                        int Node2 = ac.Node[k].Next[1];
                        dp[i][j+1][Node1][l | ac.Node[Node1].id] += dp[i][j][k][l];
                        dp[i+1][j][Node2][l | ac.Node[Node2].id] += dp[i][j][k][l];
                        dp[i][j+1][Node1][l | ac.Node[Node1].id] %= MOD;
                        dp[i+1][j][Node2][l | ac.Node[Node2].id] %= MOD;
                    }
                }
            }
        }
    }

我们可以发现：题目3其实就是题目2和题目1的结合

1.对于是给出字符数量限制的，我们一般在DP的时候加维度表示字符数量的情况：比如dp[A][T][G][C][] 前四维表示ATGC数量

2.对于是包含模式串的限制，我们一般在DP的时候加维度（二进制）表示选了哪些串m,切AC自动机的节点需要保留选串的情况

（Node[now].id |= (1<<id);）

3.我们在一些题目中还发现了，AC自动机节点是求一个（Node[now].cnt++;）这是一般问包含多少个模式窜

Node[now].falt =1;  这是标记哪些是给出的模式串    这些保留的变量是看情况而定