BZOJ2331 [SCOI2011]地板 插头DP

yts1999 posted @ 2015年8月03日 18:41 in 插头DP with tags bzoj 插头dp , 661 阅读

第一次写插头DP。。。太坑了。。。

最后被Windows下的回车符坑了。。。

WA了好几次

/**************************************************************
    Problem: 2331
    User: yts1999
    Language: C++
    Result: Accepted
    Time:868 ms
    Memory:26888 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
  
const int hmod = 0x3ffff;
const int mod = 20110520;
  
struct List {
    int st,next;
};
  
int b[0x3ffff + 1];
List l[0x100000];
char mp[110][110];
int f[2][0x100000],s[2][0x100000];
int cur = 1,pre,id,cnt[2];
  
int getint(int st) {
    int h = st & hmod;
    for (int i = b[h]; i != -1; i = l[i].next)
        if (l[i].st == st)
            return i;
    l[cnt[cur]].st = st;
    l[cnt[cur]].next = b[h];
    b[h] = cnt[cur];
    f[cur][cnt[cur]] = 0;
    s[cur][cnt[cur]] = st;
    return cnt[cur]++;
}
  
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; i++) {
        scanf("\n");
        for (int j = 0; j < m; j++) {
            char ch;
            scanf("%c",&ch);
            if (m > n)
                mp[j][i] = ch;
            else
                mp[i][j] = ch;
        }
    }
    if (m > n)
        swap(n,m);
    memset(b,-1,sizeof(b));
    f[cur][getint(0)] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            swap(cur,pre);
            cnt[cur] = 0;
            memset(b,-1,sizeof(b));
            int p = (m - j) << 1;
            int q = p - 2;
            for (int k = 0; k < cnt[pre]; k++) {
                int val = f[pre][k],last = s[pre][k];
                if (! j)
                    if (last & 3)
                        continue;
                    else
                        last >>= 2;
                int wp = (last >> p) & 3,wq = (last >> q) & 3;
                int now = last - (wp << p) - (wq << q);
                if (mp[i][j] == '*') {
                    if (! wp && ! wq)
                        f[cur][getint(now)] = (f[cur][getint(now)] + val) % mod;
                }
                else
                    if (! wp && ! wq) {
                        f[cur][getint(now | (1 << p))] = (f[cur][getint(now | (1 << p))] + val) % mod;
                        f[cur][getint(now | (1 << q))] = (f[cur][getint(now | (1 << q))] + val) % mod;
                        f[cur][getint(now | (3 << p) | (3 << q))] = (f[cur][getint(now | (3 << p) | (3 << q))] + val) % mod;
                    }
                    else
                        if (! wp || ! wq) {
                            f[cur][getint(now | (wp << q) | (wq << p))] = ( f[cur][getint(now | (wp << q) | (wq << p))] + val) % mod;
                            if (wp == 1)
                                f[cur][getint(last | (2 << p))] = (f[cur][getint(last | (2 << p))] + val) % mod;
                            else
                                if (wq == 1)
                                    f[cur][getint(last | (2 << q))] = (f[cur][getint(last | (2 << q))] + val) % mod;
                                else
                                    f[cur][getint(now)] = (f[cur][getint(now)] + val) % mod;
                        }
                        else
                            if (wp == 1 && wq == 1)
                                f[cur][getint(now)] = (f[cur][getint(now)] + val) % mod; 
            }
        }
    printf("%d\n",f[cur][getint(0)]);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter