首页 > ACM题库 > HDU-杭电 > HDU 4758-Walk Through Squares-动态规划-[解题报告]HOJ
2015
09-17

HDU 4758-Walk Through Squares-动态规划-[解题报告]HOJ

Walk Through Squares

问题描述 :

Tree

  On the beaming day of 60th anniversary of NJUST, as a military college which was Second Artillery Academy of Harbin Military Engineering Institute before, queue phalanx is a special landscape.
  
  Here is a M*N rectangle, and this one can be divided into M*N squares which are of the same size. As shown in the figure below:
  01–02–03–04
  || || || ||
  05–06–07–08
  || || || ||
  09–10–11–12
  Consequently, we have (M+1)*(N+1) nodes, which are all connected to their adjacent nodes. And actual queue phalanx will go along the edges.
  The ID of the first node,the one in top-left corner,is 1. And the ID increases line by line first ,and then by column in turn ,as shown in the figure above.
  For every node,there are two viable paths:
  (1)go downward, indicated by ‘D’;
  (2)go right, indicated by ‘R’;
  The current mission is that, each queue phalanx has to walk from the left-top node No.1 to the right-bottom node whose id is (M+1)*(N+1).
In order to make a more aesthetic marching, each queue phalanx has to conduct two necessary actions. Let’s define the action:
  An action is started from a node to go for a specified travel mode.
  So, two actions must show up in the way from 1 to (M+1)*(N+1).

  For example, as to a 3*2 rectangle, figure below:
    01–02–03–04
    || || || ||
    05–06–07–08
    || || || ||
    09–10–11–12
  Assume that the two actions are (1)RRD (2)DDR

  As a result , there is only one way : RRDDR. Briefly, you can not find another sequence containing these two strings at the same time.
  If given the N, M and two actions, can you calculate the total ways of walking from node No.1 to the right-bottom node ?

输入:

  The first line contains a number T,(T is about 100, including 90 small test cases and 10 large ones) denoting the number of the test cases.
  For each test cases,the first line contains two positive integers M and N(For large test cases,1<=M,N<=100, and for small ones 1<=M,N<=40). M denotes the row number and N denotes the column number.
  The next two lines each contains a string which contains only ‘R’ and ‘D’. The length of string will not exceed 100. We ensure there are no empty strings and the two strings are different.

输出:

  The first line contains a number T,(T is about 100, including 90 small test cases and 10 large ones) denoting the number of the test cases.
  For each test cases,the first line contains two positive integers M and N(For large test cases,1<=M,N<=100, and for small ones 1<=M,N<=40). M denotes the row number and N denotes the column number.
  The next two lines each contains a string which contains only ‘R’ and ‘D’. The length of string will not exceed 100. We ensure there are no empty strings and the two strings are different.

样例输入:

2
3 2
RRD
DDR
3 2
R
D

样例输出:

1
10

           AC自动机+DP。想了很久都没想出来。。。据说是一道很模板的自动机dp。。。Walk Through Squares原来自动机还可以这么跑啊。。。我们先用两个字符串建自动机,然后就是建一个满足能够从左上角到右下角的新串,这样我们直接从自动机中跑出一个满足题意的串就可以了,(貌似需要建新串的AC+DP都需要这么搞啊!)可以利用chd数组去递推得到状态的种数。这里我们用dp[
i ][ j ][ k ][ s ]表示当字符的位置为在矩阵中位置为(i, j)时,及向右走了 i 次,向下走了 j 次,时到达自动机上下标为k 的节点时状态为 s (1表示有串1,2表示有串2,3表示两个串都有)的种数。

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;
typedef long long LL;

const int MAX_NODE = 110 * 2;
const int MOD = 1000000007;
const int CHILD_NUM = 2;
const int N = 110;

class ACAutomaton
{
private:
    int chd[MAX_NODE][CHILD_NUM];
    int dp[2][N][MAX_NODE][4];
    int fail[MAX_NODE];
    int val[MAX_NODE];
    int Q[MAX_NODE];
    int ID[128];
    int sz;
public:
    void Initialize()
    {
        fail[0] = 0;
        ID['R'] = 0;
        ID['D'] = 1;
    }
    void Reset()
    {
        CLR(chd[0] , 0);
        CLR(val, 0);
        sz = 1;
    }
    void Insert(char *a, int hav)
    {
        int p = 0;
        for ( ; *a ; a ++)
        {
            int c = ID[*a];
            if (!chd[p][c])
            {
                memset(chd[sz] , 0 , sizeof(chd[sz]));
                chd[p][c] = sz ++;
            }
            p = chd[p][c];
        }
        val[p] |= hav;
    }
    void Construct()
    {
        int *s = Q , *e = Q;
        for (int i = 0 ; i < CHILD_NUM ; i ++)
        {
            if (chd[0][i])
            {
                fail[chd[0][i]] = 0;
                *e ++ = chd[0][i];
            }
        }
        while (s != e)
        {
            int u = *s++;
            for (int i = 0 ; i < CHILD_NUM ; i ++)
            {
                int &v = chd[u][i];
                if (v)
                {
                    *e ++ = v;
                    fail[v] = chd[fail[u]][i];
                    val[v] |= val[fail[v]];
                }
                else
                {
                    v = chd[fail[u]][i];
                }
            }
        }
    }
    int Work(int n, int m)
    {
        //最好手动初始化dp数组,不然如果没有用滚动数组的话会超时。
        for(int j = 0; j <= m; j ++)
                for(int k = 0; k < sz; k ++)
                    for(int s = 0; s < 4; s ++)
                        dp[0][j][k][s] = 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 < sz; k ++)
                    for(int s = 0; s < 4; s ++)
                        dp[(i + 1) & 1][j][k][s] = 0;
            for(int j = 0; j <= m; j ++)
                for(int k = 0; k < sz; k ++)
                    for(int s = 0; s < 4; s ++)
                    {
                        if(i < n)
                        {
                            int next = chd[k][0];
                            int tmp = s | val[next];
                            dp[(i + 1) & 1][j][next][tmp] += dp[i & 1][j][k][s];
                            dp[(i + 1) & 1][j][next][tmp] %= MOD;
                        }
                        if(j < m)
                        {
                            int next = chd[k][1];
                            int tmp = s | val[next];
                            dp[i & 1][j + 1][next][tmp] += dp[i & 1][j][k][s];
                            dp[i & 1][j + 1][next][tmp] %= MOD;
                        }
                    }
        }
        int ret = 0;
        for(int i = 0; i < sz;i ++)
        {
            ret = (ret + dp[n & 1][m][i][3]) % MOD;
        }
        return ret;
    }
} AC;

int main()
{
    //freopen("input.txt", "r", stdin);
    AC.Initialize();
    int n, t, m;
    scanf("%d", &t);
    while (t --)
    {
        AC.Reset();
        scanf("%d%d", &n, &m);
        for (int i = 1 ; i <= 2 ; i ++)
        {
            char temp[N];
            scanf("%s", temp);
            AC.Insert(temp, i);
        }
        AC.Construct();
        printf("%d\n", AC.Work(n, m));
    }
    return 0;
}

参考:http://blog.csdn.net/ok_again/article/details/12448979