首页 > 代码库 > 插头DP
插头DP
何为插头DP？
顾名思义，对插头做DP（逃，插头DP一般应用于棋盘模型类的问题，处理连通性之类的东西，系统的学习还是要看CDQ的那个PPT，我这里只记一下题解和一些思路。
COGS1512
Ural的用户体验差评，所以在COGS上交了第一道插头DP的模板题。刚开始看ppt的时候看到这道题即使看了题解也不是很有思路，当时局限于怎么实现逐行转移和首尾边界的处理。看了一下别人的模板，看了很长时间才明白CDQ在起初强调轮廓线的含义。其实对轮廓线的DP已经是下一状态的处理状态。再来就是逐行转移，其实这个也很好处理，只需要把轮廓线的状态前移两位//3进制的4进制表示，然后就可以模拟出第一位的最左边无插头，剩下的只要按照CDQ的各种状况逐个处理就行了。
1 //COGS 1512 Ural 1519 2 // cha tou DP by Cydiater 3 //2016.8.25 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <cstdio> 9 #include <cstdlib> 10 #include <iomanip> 11 #include <ctime> 12 #include <cmath> 13 #include <queue> 14 #include <map> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n) for(ll i=j;i<=n;i++) 18 #define down(i,j,n) for(ll i=j;i>=n;i--) 19 #define FILE "formula1" 20 const ll MAXN=600000+5; 21 const ll LIM=1<<15; 22 const ll mod=LIM-1; 23 const ll oo=0x3f3f3f3f; 24 inline ll read(){ 25 char ch=getchar();ll x=0,f=1; 26 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 27 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 28 return x*f; 29 } 30 ll N,M,sta=0,ex,ey; 31 bool flag[25][25]; 32 struct Hash{ 33 ll LINK[LIM],len,S[MAXN],v[MAXN],next[MAXN]; 34 void clr(){ 35 memset(LINK,0,sizeof(LINK)); 36 len=0; 37 } 38 void insert(ll s,ll va){ 39 ll head=s&mod; 40 for(ll i=LINK[head];i;i=next[i])if(S[i]==s){ 41 v[i]+=va; 42 return; 43 } 44 next[++len]=LINK[head];LINK[head]=len;S[len]=s;v[len]=va; 45 } 46 }f[2]; 47 namespace solution{ 48 inline ll BIT(ll head,ll pos){ 49 pos<<=1; 50 return head<<pos; 51 } 52 inline ll getbit(ll s,ll pos){ 53 ll tmp=s&(3<<(pos<<1)); 54 return tmp>>(pos<<1); 55 } 56 inline ll creatbit(ll s,ll pos1,ll pos2){ 57 pos1<<=1;pos2<<=1; 58 pos1=~(3<<pos1);pos2=~(3<<pos2); 59 return s&pos1&pos2; 60 } 61 inline ll getR(ll s,ll pos){ 62 ll cnt=1; 63 up(i,pos+1,M){ 64 ll tmp=(s&(3<<(i<<1)))>>(i<<1); 65 if(tmp==1)cnt++; 66 else if(tmp==2)cnt--; 67 if(cnt==0)return i; 68 } 69 return -1; 70 } 71 inline ll getL(ll s,ll pos){ 72 ll cnt=1; 73 down(i,pos-1,0){ 74 ll tmp=(s&(3<<(i<<1)))>>(i<<1); 75 if(tmp==1)cnt--; 76 else if(tmp==2)cnt++; 77 if(cnt==0)return i; 78 } 79 return -1; 80 } 81 void init(){ 82 N=read();M=read(); 83 memset(flag,0,sizeof(flag)); 84 up(i,1,N){ 85 up(j,1,M){ 86 char ch;scanf(" %c",&ch); 87 flag[i][j]=ch==‘*‘?0:1; 88 } 89 } 90 up(i,1,N)up(j,1,M)if(flag[i][j]){ 91 ex=i;ey=j; 92 } 93 } 94 void slove(){ 95 f[sta].clr();f[sta].insert(0,1); 96 up(i,1,N){ 97 sta^=1;f[sta].clr(); 98 up(j,1,f[sta^1].len) 99 f[sta].insert(f[sta^1].S[j]<<2,f[sta^1].v[j]);100 up(j,1,M){101 sta^=1;f[sta].clr();102 up(k,1,f[sta^1].len){103 ll leftt=getbit(f[sta^1].S[k],j-1);104 ll upp=getbit(f[sta^1].S[k],j);105 ll s=creatbit(f[sta^1].S[k],j,j-1);106 if(leftt==0&&upp==0){107 if(!flag[i][j])f[sta].insert(s,f[sta^1].v[k]);108 else if(flag[i+1][j]&&flag[i][j+1]&&i<N&&j<M)109 f[sta].insert(s|BIT(1,j-1)|BIT(2,j),f[sta^1].v[k]);110 }else if(leftt==0||upp==0){111 ll tmp=leftt?leftt:upp;112 if(i<N&&flag[i+1][j])f[sta].insert(s|BIT(tmp,j-1),f[sta^1].v[k]);113 if(j<M&&flag[i][j+1])f[sta].insert(s|BIT(tmp,j),f[sta^1].v[k]);114 }115 else if(leftt==1&&upp==1)f[sta].insert(s^BIT(3,getR(s,j)),f[sta^1].v[k]);116 else if(leftt==2&&upp==2)f[sta].insert(s^BIT(3,getL(s,j-1)),f[sta^1].v[k]);117 else if(leftt==2&&upp==1)f[sta].insert(s,f[sta^1].v[k]);118 else if(i==ex&&j==ey)f[sta].insert(s,f[sta^1].v[k]);119 }120 }121 }122 }123 void output(){124 up(i,1,f[sta].len)if(f[sta].S[i]==0){125 cout<<f[sta].v[i]<<endl;126 return;127 }128 puts("0");129 }130 }131 int main(){132 freopen(FILE".in","r",stdin);133 freopen(FILE".out","w",stdout);134 //freopen("input.in","r",stdin);135 using namespace solution;136 init();137 slove();138 output();139 return 0;140 }
插头DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。