再谈 插头动规 POJ1739 Tony’s tour

上次我已经分析过这个问题了。这里我为了查阅方便,转载了一下陈丹琦同学的论文。如有侵权,联系即删。

果然……写论文就是要严谨。我最近发现了楼教主的男人八题是个好东西,果断开始学习之。今天早上忽然心血来潮,决定做一回“男人”,攻克POJ1739 Tony’s tour。

POJ1739 Tony’s tour

这道题稍微转化一下,在最后面加两行:

.#######.
.........

就是经典的插头DP问题了。所以用4base括号表示法应该会比较好。考虑到hash的问题,m是小于等于8的,也就是16位,216=655362^{16}=65536,利用滚动数组的思想,开一个f[2][65536]的数组就好了,内存为512K,小于题目限制。

编码完成,开始调试了。主要问题都出在计算完一遍之后继续计算的时候没有重置所有的东西,这一点以后要注意了。提交第一次:Runtime Error。回来检查发现8*8会挂掉。输出调试信息之后发现这个f数组开的不够大,可是为什么呢??前面如此严谨计算竟然会出现不够大的情况!

然而我忘了除了八个格子以外还有一个侧着的格子……所以是229=2621442^{2*9}=262144,数组开小了,这也是需要记住的。

AC了!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define setplug(d,s) plug[0]=s,plug[y]=d,hq[!r].enqueue(plug,f[r][hq[r].code]);
using namespace std;
int m,n,f[2][262144];
bool r,last=false;
struct hashqueue{
    int code;
    queue<int>q;
    bool p;
    void enqueue(int plug[],int amount){
        code=0;
        for(int i=0;i<=n;i++){
            code=(code<<2)|plug[i];
        }
        if(!f[p]){
            q.push(code);
        }
        f[p]+=amount;
    }
    void dequeue(int plug[]){
        code=q.front();
        q.pop();
        for(int i=n;i>=0;i--){
            plug[i]=(code>>(n-i<<1))&3;
        }
    }
    void clear(){
        while(!q.empty()){
            q.pop();
        }
    }
}hq[2];
inline void transfer(int y){
    int plug[n+1],amount;
    while(!hq[r].q.empty()){
        hq[r].dequeue(plug);
        switch(plug[0]){
            case 0:{
                switch(plug[y]){
                    case 0:{
                        setplug(1,2);
                        break;
                    }
                    case 1:{
                        setplug(1,0);
                        setplug(0,1);
                        break;
                    }
                    case 2:{
                        setplug(2,0);
                        setplug(0,2);
                        break;
                    }
                }
                break;
            }
            case 1:{
                switch(plug[y]){
                    case 0:{
                        setplug(0,1);
                        setplug(1,0);
                        break;
                    }
                    case 1:{
                        int match=y,cnt=1;
                        while(cnt){
                            match++;
                            if(plug[match]==1){
                                cnt++;
                            }else if(plug[match]==2){
                                cnt--;
                            }
                        }
                        plug[match]=1;
                        setplug(0,0);
                        break;
                    }
                    case 2:{
                        if(last){
                            setplug(0,0);
                        }
                        break;
                    }
                }
                break;
            }
            case 2:{
                switch(plug[y]){
                    case 0:{
                        setplug(2,0);
                        setplug(0,2);
                        break;
                    }
                    case 1:{
                        setplug(0,0);
                        break;
                    }
                    case 2:{
                        int match=y,cnt=1;
                        while(cnt){
                            match--;
                            if(plug[match]==1){
                                cnt--;
                            }else if(plug[match]==2){
                                cnt++;
                            }
                        }
                        plug[match]=2;
                        setplug(0,0);
                        break;
                    }
                }
                break;
            }
        }
    }
}
inline void block(int y){
    int plug[n+1],amount;
    while(!hq[r].q.empty()){
        hq[r].dequeue(plug);
        if(plug[0]==0&&plug[y]==0){
            hq[!r].enqueue(plug,f[r][hq[r].code]);
        }
    }
}
inline void newline(){
    memset(f[!r],0,sizeof(f[!r]));
    int plug[n+1],amount;
    while(!hq[r].q.empty()){
        hq[r].dequeue(plug);
        if(plug[0]==0){
            hq[!r].enqueue(plug,f[r][hq[r].code]);
        }
    }
    r=!r;
}
inline int solve(char op,int j){
    memset(f[!r],0,sizeof(f[!r]));
    if(op=='.'){
        transfer(j);
    }else{
        block(j);
    }
    r=!r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    char op;
    hq[0].p=0;
    hq[1].p=1;
    for(cin>>m>>n;m&&n;cin>>m>>n){
        hq[0].clear(),hq[1].clear();
        last=false;
        memset(f,0,sizeof(f));
        int plug[n+1];
        memset(plug,0,sizeof(plug));
        hq[r].enqueue(plug,1);
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin>>op;
                solve(op,j);
            }
            newline();
        }
        solve('.',1);
        for(int j=2;j<n;j++){
            solve('#',j);
        }
        solve('.',n);
        newline();
        for(int j=1;j<n;j++){
            solve('.',j);
        }
        last=true;
        solve('.',n);
        cout<<f[r][0]<<endl;
    }
}

做完这题,感到心旷神怡,神清气爽!我其实是在阅读了很多网友写的论文以及感想之后,经常在闲暇时间仔细思考,我才做出来的,对我而言意义重大。

当然我的代码十分拙略,常数稍大。几个主要存在的问题:

  • hash做的不够 。什么叫不够,明明就没有hash,直接开了一个数组存进去。这对再大一点点(10~12)的图就会超空间。这次使用了2000K,有点悬。
  • 最后的那个左下入右下出我直接添加了两行图上去,虽然能够得到答案,但是其实没有必要。事实上相当于在结束的时候在且仅在1和n号位置有插头就得出了答案。
  • 两层switch直接枚举情况。其中一些应该是可以合并来处理的,不过看论文中好像也没有合并多少。
    如有其他的问题以及更好的写法,请大牛们斧正!
avatar
Kerry Su