BZOJ2331 [SCOI2011]地板
插头DP    2016-09-24 19:24:59    328    1    0
jszyxw   插头DP

Description

 

lxhgwws的小名叫“小L”,这是因为他总是很喜欢L型的东西。小L家的客厅是一个R*C的矩形,现在他想用L型的地板来铺满整个客厅,客厅里有些位置有柱子,不能铺地板。现在小L想知道,用L型的地板铺满整个客厅有多少种不同的方案?

需要注意的是,如下图所示,L型地板的两端长度可以任意变化,但不能长度为0。铺设完成后,客厅里面所有没有柱子的地方都必须铺上地板,但同一个地方不能被铺多次。

Input

输入的第一行包含两个整数,R和C,表示客厅的大小。

接着是R行,每行C个字符。’_’表示对应的位置是空的,必须铺地板;’*’表示对应的位置有柱子,不能铺地板。

Output

输出一行,包含一个整数,表示铺满整个客厅的方案数。由于这个数可能很大,只需输出它除以20110520的余数。

Sample Input

2 2

*_

__

Sample Output

1

HINT

R*C<=100

 

Solution

第一次写插头DP...

看的是CDQ的论文.然后自己yy了一下

写了两个晚上+一个下午..整个人都不好了

思路大概就是0表示没有插头,1表示有一个没有拐过弯的插头,2表示有一个拐过弯的插头,具体转移的话可以看代码

用四进制存状态速度较快,在我的代码里,第一位存左插头,2~m+1位存'上插头的队列',这样转移比较方便

注意换行的时候,不要转移包含左插头的状态.

思路非常简单,实现非常鬼畜......

 

#include <bits/stdc++.h>
using namespace std;
const int mo = 20110520;
const int maxm = 11;
const int maxn = 101;
const int maxs = 5e6;

int n, m;
int dp[2][maxs];

int bound = 1;

bool a[maxn][maxn];

inline int change(register int x, register int up, register int left)
{
    x >>= 4;
    x <<= 2;
    return x | left | up * bound;
}


int main()
{
    if (fopen("2331.in", "r") != NULL) {
        freopen("2331.in", "r", stdin);
        freopen("2331.out", "w", stdout);
    }

    cin >> n >> m;

    char s[maxn];
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; ++ j) {
            (n < m ? a[j][i] : a[i][j]) = s[j] == '*';
        }
    }
    if (n < m) swap(n, m);

    for (int i = 1; i <= (m << 1); ++ i) {
        bound <<= 1;
    }

    int MAXSTATUS = 1 << (2 * m + 2);

    static int now;
    static int pre = 1;

    dp[now][0] = 1;

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            now ^= 1;
            pre ^= 1;
            memset(dp[now], 0, sizeof dp[now]);
            if (a[i][j]) {
                for (register int k = 0; k < MAXSTATUS; k += 16) if (dp[pre][k]) {
                    (dp[now][change(k, 0, 0)] += dp[pre][k]) %= mo;
                }
            }
            else {
                for (register int k = 0; k < MAXSTATUS; ++ k) if (dp[pre][k]) {

                    register int left = k % 4;
                    register int up = k / 4 % 4;

                    if (j == 1 && left) continue;

                    if (left == 0 && up == 0) {
                        (dp[now][change(k, 0, 1)] += dp[pre][k]) %= mo;
                        (dp[now][change(k, 1, 0)] += dp[pre][k]) %= mo;
                        (dp[now][change(k, 2, 2)] += dp[pre][k]) %= mo;
                    }
                    else 
                    if (left == 1 && up == 0) {
                        (dp[now][change(k, 0, 1)] += dp[pre][k]) %= mo;
                        (dp[now][change(k, 2, 0)] += dp[pre][k]) %= mo;
                    }
                    else 
                    if (left == 2 && up == 0) {
                        (dp[now][change(k, 0, 2)] += dp[pre][k]) %= mo;
                        (dp[now][change(k, 0, 0)] += dp[pre][k]) %= mo;
                    }
                    else 
                    if (left == 0 && up == 1) {
                        (dp[now][change(k, 1, 0)] += dp[pre][k]) %= mo;
                        (dp[now][change(k, 0, 2)] += dp[pre][k]) %= mo;
                    }
                    else 
                    if (left == 1 && up == 1) {
                        (dp[now][change(k, 0, 0)] += dp[pre][k]) %= mo;
                    }
                    else 
                    if (left == 0 && up == 2) {
                        (dp[now][change(k, 2, 0)] += dp[pre][k]) %= mo;
                        (dp[now][change(k, 0, 0)] += dp[pre][k]) %= mo;
                    }
                }
            }
        }

    cout << dp[now][0] << endl;

    return 0;
}

 

打完之后发现会爆内存,然后开滚动数组

然后发现滚动数组清空非常慢,每次枚举的无用状态太多,于是我们用hash表

 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 101;
const int mo = 20110520;
const int size = 2e5 + 7;
const int maxstatus = 5e6;

int n, m;
int bound = 1;
bool a[maxn][maxn];

inline int change(register int x, register int up, register int left)
{
    x >>= 4; x <<= 2;
    return x | left | up * bound;
}

struct Hash_table
{
    int cnte;
    int st[size];
    int dp[maxstatus];
    int next[maxstatus];

    inline void clear()
    {
        cnte = 0;
        memset(st, -1, sizeof st);
    }

    inline void Add(register int x, register int v)
    {
        register int u = x % size;
        for (register int i = st[u]; ~i; i = next[i]) {
            if (i == x) {
                (dp[x] += v) %= mo;
                return ;
            }
        }
        next[x] = st[u];
        st[u] = x;
        dp[x] = v;
    }

    inline int Find(int x)
    {
        int u = x % size;
        for (int i = st[u]; ~i; i = next[i]) {
            if (i == x)
                return dp[x];
        }
        return 0;
    }

} dp[2];

int main()
{
    if (fopen("2331.in", "r") != NULL) {
        freopen("2331.in", "r", stdin);
        freopen("2331.out", "w", stdout);
    }

    cin >> n >> m;

    char s[maxn];
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; ++ j) {
            (n < m ? a[j][i] : a[i][j]) = s[j] == '*';
        }
    }
    if (n < m) swap(n, m);

    for (int i = 1; i <= (m << 1); ++ i) {
        bound <<= 1;
    }

    static int now;
    static int pre = 1;

    memset(dp[0].next, -1, sizeof dp[0].next);
    memset(dp[1].next, -1, sizeof dp[1].next);
    dp[now].clear();
    dp[now].Add(0, 1);

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            now ^= 1;
            pre ^= 1;
            dp[now].clear();
            if (a[i][j]) {
                for (register int _ = 0; _ < size; ++ _)
                    for (register int v = dp[pre].st[_]; ~v; v = dp[pre].next[v]) {
                        if (v % 16 == 0) 
                            dp[now].Add(change(v, 0, 0), dp[pre].dp[v]);
                    }
            }
            else {
                for (register int _ = 0; _ < size; ++ _)
                    for (register int k = dp[pre].st[_]; ~k; k = dp[pre].next[k]) {

                        register int val = dp[pre].dp[k];

                        register int left = k % 4;
                        register int up = k / 4 % 4;

                        if (j == 1 && left) continue;

                        if (left == 0 && up == 0) {
                            dp[now].Add(change(k, 0, 1), val);
                            dp[now].Add(change(k, 1, 0), val);
                            dp[now].Add(change(k, 2, 2), val);
                        }
                        else 
                        if (left == 1 && up == 0) {
                            dp[now].Add(change(k, 0, 1), val);
                            dp[now].Add(change(k, 2, 0), val);
                        }
                        else 
                        if (left == 2 && up == 0) {
                            dp[now].Add(change(k, 0, 2), val);
                            dp[now].Add(change(k, 0, 0), val);
                        }
                        else 
                        if (left == 0 && up == 1) {
                            dp[now].Add(change(k, 1, 0), val);
                            dp[now].Add(change(k, 0, 2), val);
                        }
                        else 
                        if (left == 1 && up == 1) {
                            dp[now].Add(change(k, 0, 0), val);
                        }
                        else 
                        if (left == 0 && up == 2) {
                            dp[now].Add(change(k, 2, 0), val);
                            dp[now].Add(change(k, 0, 0), val);
                        }
                    }
            }
        }

    cout << dp[now].Find(0) << endl;
}

 

好像这是独立插头..感觉身体被掏空..

OI template
328 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航