URAL1519 HOJ1712 插头DP小入门_Dark~gt_百度空间企业库|免费b2b网站

URAL1519 HOJ1712 插头DP小入门_Dark~gt_百度空间

Cdq的论文，这个人人皆知。但是她的那个ppt里状态转移很多地方说的不是很明白，结果弄了好久才弄明白。zero有份“很珍贵”的doc版论文，据说里面说的很清楚。。。

目前只做了简单3进制的回路问题

自我感觉PPT里没提到的几点：

1、分量合并的时候，还有一种情况是（））变为）# #

2、分量合并的时候，比如（））这种，左面那个（不一定是紧挨着{dy}个）的

3、（）变成##，仅在{zh1}一格，这个不看不知道啊。。。

为什么要用hash？可不可以不用hash？

因为3进制的话，很多状态都是不合法的，在3^13里面合法状态只有4w多一点。想到什么了？unsigned short！对于HOJ1712，合法状态不超过6k，short就够了。

不过事实证明枚举合法状态没有hash来的快，可能是因为数组太大，取数的时候效率低的缘故

3进制还是4进制？

4进制可以位运算提高速度，但是相当卡内存，必须配合上述只枚举合法状态的方法。不过代码写出来不是很好看。。。

鉴于以后的4进制哈密顿路，5进制普通路，以及多进制联通块问题，还是留个3进制的模板吧。

PS：wa一晚上加一上午发现URAL是用I64d的。。。

URAL1519：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char g[17][17];
#define For(i,n) for(i=0;i<(n);i++)
#define f5(s) dp[t][s]=dp[t][s]==-1?dp[p][kk]:dp[t][s]+dp[p][kk]
long long dp[2][42000], ans;
int dig[15] = {1}, tot = 0, t, p, ansx, ansy;
unsigned short ts[1600000];
int st[42000];

bool check(int num)
{
    int cnt = 0;
    while (num)
    {
        int k = num % 3;
        if (k == 1) cnt++;
        if (k == 2) cnt--;
        num /= 3;
        if (cnt < 0) return false;
    }
    if (cnt != 0) return false;
    return true;
}

int getbit(int k, int j)
{
    while (j-- > 0)
    {
        k /= 3;
    }
    return k % 3;
}

int main()
{
    int i, j, n, m, k, kk;
    for (i = 1; i < 15; i++) dig[i] = dig[i - 1]*3;
    For(i, dig[13])
    {
        if (check(i))
        {
            ts[i] = tot;
            st[tot++] = i;
        }
        else ts[i] = 50000;
    }
    st[tot++] = 999999999;
    scanf("%d%d", &n, &m);
    ans = 0;
    For(i, n)
    {
        scanf("\n%s", g[i]);
        For(j, m)
        if (g[i][j] == '.') ansx = i, ansy = j;
    }
    memset(dp, -1, sizeof (dp));
    dp[t = 0][0] = 1;

    For(i, n)
    {
        For(j, m)
        {
            t ^= 1, p = 1 - t;
            memset(dp[t], -1, sizeof (dp[t]));
            for (kk = 0; (k = st[kk]) < dig[m + 1]; kk++)
            {
                if (dp[p][kk] != -1)
                {
                    int l = getbit(k, j);
                    int u = getbit(k, j + 1);
                    int pre = k - l * dig[j] - u * dig[j + 1];
                    if (g[i][j] != '.')
                    {
                        if (l == 0 && u == 0) f5(kk);
                        continue;
                    }
                    if (l == 0 && u == 0&&g[i+1][j] == '.'&&g[i][j+1] == '.') f5(ts[pre + 1 * dig[j] + 2 * dig[j + 1]]);
                    if (l + u == 3)
                    {
                        if (l == 1 && u == 2)
                        {
                            if (i == ansx && j == ansy&&pre==0)
                            {
                                ans += dp[p][kk];
                            }
                            continue;
                        }
                        f5(ts[pre]);
                    }
                    if ((l != 0 && u == 0) || (l == 0 && u != 0))
                    {
                        if (g[i+1][j]=='.') f5(ts[pre + (u + l) * dig[j]]);
                        if (g[i][j+1]=='.')f5(ts[pre + (u + l) * dig[j + 1]]);
                    }
                    if (l == 1 && u == 1)
                    {
                        int cnt = 1;
                        for (int jj = j + 2; jj < m + 1; jj++)
                        {
                            int e = getbit(k, jj);
                            if (e == 2) cnt--;
                            if (e == 1) cnt++;
                            if (cnt == 0)
                            {
                                f5(ts[pre - 2 * dig[jj] + 1 * dig[jj]]);
                                break;
                            }
                        }
                    }
                    if (l == 2 && u == 2)
                    {
                        int cnt = 1;
                        for (int jj = j - 1; jj >= 0; jj--)
                        {
                            int e = getbit(k, jj);
                            if (e == 1) cnt--;
                            if (e == 2) cnt++;
                            if (cnt == 0)
                            {
                                f5(ts[pre - 1 * dig[jj] + 2 * dig[jj]] );
                                break;
                            }
                        }
                    }
                }
            }
        }
        t ^= 1, p = 1 - t;
        memset(dp[t], -1, sizeof (dp[t]));
        for (kk = 0; (k = st[kk]) < dig[m]; kk++)
        {
            j = k * 3;
            dp[t][ts[j]] = dp[p][kk];
        }
    }
    printf("%I64d\n", ans);
}

郑重声明：资讯【URAL1519 HOJ1712 插头DP小入门_Dark~gt_百度空间】由发布，版权归原作者及其所在单位，其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实，请读者仅作参考，并请自行核实相关内容。若本文有侵犯到您的版权，请你提供相关证明及申请并与我们联系（qiyeku # qq.com）或【在线投诉】，我们审核后将会尽快处理。

—— 相关资讯 ——