poj 1739 Tony's Tour 插头dp
第一道插头dp，还是非常艰难的，做法的话cdq论文中已经讲得很清楚了，用的是最小表示法，但是这个题目因为障碍的存在导致细节处理上面更加麻烦。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=9,maxm=3e3+9;;char a[maxn][maxn];bool first[9][9];int n,m;int cag(int txt){ int ss[11]; int lon=-1; while(txt) { ss[++lon]=txt%8; txt/=8; } short fla[11],top=0; memset(fla,0,sizeof(fla)); for(int i=0;i<=lon;i++) if(ss[i]) { if(!fla[ss[i]]) { fla[ss[i]]=++top; ss[i]=top; } else ss[i]=fla[ss[i]]; } txt=0; int tt=1; for(int i=0;i<=lon;i++) { txt+=ss[i]*tt; tt*=8; } return txt;}struct{ int hash[maxm],lon; struct { int key,next; long long sum; }data[maxm]; void clear() { memset(hash,-1,sizeof(hash)); lon=0; } void push(int key,long long sum) { key=cag(key);// cout<<key<<endl; int tmp=key%maxm; for(int k=hash[tmp];k!=-1;k=data[k].next) { if(data[k].key==key) { data[k].sum+=sum; return ; } } data[++lon].key=key; data[lon].sum=sum; data[lon].next=hash[tmp]; hash[tmp]=lon; }}dp[2];int getbit(int tmp,int k){ tmp=(tmp&(7<<k*3)); return tmp>>k*3;}int cal(int tmp){ int ans=0; while(tmp) { ans=max(ans,tmp%8); tmp/=8; } return ans+1;}int ss[11];int mer(int tmp,int t,int s){ int txt=tmp,lon=-1; while(txt) { ss[++lon]=txt%8; txt/=8; }// cout<<endl;// printf("%d %d\n",t,s);// for(int i=0;i<=lon;i++)// printf("%d",ss[i]);// cout<<endl; int a=ss[t],b=ss[s]; int c=max(a,b); int d=min(a,b); ss[t]=0; ss[s]=0; for(int i=0;i<=lon;i++) if(ss[i]==c) ss[i]=d;// for(int i=0;i<=lon;i++)// printf("%d",ss[i]);// cout<<endl; txt=0; int tt=1; for(int i=0;i<=lon;i++) { txt+=ss[i]*tt; tt*=8; } return txt;}int ff(int tmp){ if(tmp==0) return tmp; int txt=tmp,lon=-1; while(txt) { ss[++lon]=txt%8; txt/=8; } int i,j; for(i=0;i<=lon;i++) if(ss[i]) break; for(j=lon;j>=0;j--) if(ss[i]) break; ss[i]=ss[j]; txt=0; int tt=1; for(int i=0;i<=lon;i++) { txt+=ss[i]*tt; tt*=8; } return txt;}void solve(){ int now=0,pre=1; dp[now].clear(); dp[pre].clear(); for(int i=n;i>=1;i--) for(int j=1;j<=m;j++) { now=now^1; pre=pre^1; dp[now].clear();// cout<<dp[pre].lon<<endl; if(a[i][j]=='#') { for(int k=1;k<=dp[pre].lon;k++) { int tmp=dp[pre].data[k].key; long long sum=dp[pre].data[k].sum; int up=getbit(tmp,j); int r=getbit(tmp,0); if(!up&&!r) dp[now].push(tmp,sum); } continue; } if(i==n&&j==1) { dp[pre].push(1,1); } for(int k=1;k<=dp[pre].lon;k++) { int tmp=dp[pre].data[k].key; long long sum=dp[pre].data[k].sum; int up=getbit(tmp,j); int r=getbit(tmp,0);// for(int p=0;p<=m;p++)// printf("%d",getbit(tmp,p));// printf("\n");// if(i==1&&j==m)// printf("%d %d %d %d %d %d\n\n",i,j,up,r,tmp,sum); if(tmp==0) continue; if(up&&r) { if(up!=r) dp[now].push(mer(tmp,j,0),sum); else if(first[i][j]) dp[now].push(mer(tmp,j,0),sum); } else if(up&&!r) { if(j!=m) dp[now].push(tmp-(up<<j*3)+up,sum);// else if(j==m&&i==n)// dp[now].push(tmp-(up<<j*3),sum); if(j!=m||i!=n) if(i!=1) dp[now].push(tmp,sum); } else if(!up&&r) { if(j!=m||i!=n) if(i!=1) dp[now].push(tmp+(r<<j*3)-r,sum); if(j!=m) dp[now].push(tmp,sum); else if(j==m&&i==n) { int txt=ff(tmp-r); dp[now].push(txt,sum); } } else if(!up&&!r) { if(j!=m&&i!=1) dp[now].push(tmp+((cal(tmp))<<j*3)+cal(tmp),sum); else if(j==m&&i==n) { int txt=ff(tmp+((cal(tmp))<<j*3)); dp[now].push(txt,sum); } } } } long long ans=0; for(int i=1;i<=dp[now].lon;i++) if(dp[now].data[i].key==0) ans+=dp[now].data[i].sum; cout<<ans<<endl;}int main(){// freopen("in.txt","r",stdin); while(scanf("%d %d",&n,&m)!=EOF) { if(n==0&&m==0) break; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%c",&a[i][j]); if(a[i][j]==' '||a[i][j]=='\n') j--; } memset(first,0,sizeof(first)); for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) if(a[i][j]=='.') { first[i][j]=1; i=n+1; break; } solve(); } return 0;}