虽然hsjdsn发送了插头dp的资料，但是没有学习过。 (料理啊。 这个很难入门。 只有把两个资料组合起来才能知道。 但是入门的问题没有a。 a是更简单的) emmmmmmmm )。 菜太多了。
orz这两个人的聚会：入门问题详细代码https://blog.csdn.net/lit ble/article/details/79369147
太古cdq汇集的论文3359 wenku.Baidu.com/view/9 CFBB 16 e 011 ca 300 a6 c 390 d5. html？ qq-pf-to=pcqq.group
插头dp应用：超小数据范围、网格图、连接性。
这是因为对于状态压缩的dp来说，考虑到连接性，在正常状态压缩状态下不能满足插头，并且在这种情况下，需要维持该行的逐点连接性。 轮廓线是n 1个围墙，也就是网格之间的边的状态，每次通过栓塞迁移时都可以得到以下结果的轮廓线，在得到最终结果的轮廓线总数时得到答案。
hdu1693：
在一个网格中，各非障碍点被一个圈包围，求出这些圈不重叠而相连的种类数。
玩的樱桃，就当成插头吧。
如果最初的轮廓线为0，则最终如果轮廓线的状态为0，则成为总答案。 1，1的插头只能转移到00
# include bits/stdc.husingnamespacestd； 泰普德夫龙龙LL； const LL LIM=300005，Has=299989； LL n，m，e1，e2，las，now，tt； LL ans； LL mp[15][15]，rrddm[15]，tot[2]； LL js[2][LIM]； LL h[300005]，a[2][LIM]，ne[LIM]； //tot:状态总数、js:该状态的计划总数、a:各种状态voidins(llzt，LL num ) )//卓越的散列技术LL tmp=zt%Has 1； for(LLI=h[tmp]； I； I=ne[I](if ) a[now][I]==ZT ) {js[now][i]=num； 返回； } ne[ tot[now]]=h[tmp]，h[tmp]=tot[now]； a[now][tot[now]]=zt，js[now][tot[now]]=num； }void work () { tot[now]=1，js[now][1]=1，a[now][1]=0； //初始状态为0，个数为1for(LLI=1； i=n； I ) for(llj=1； j=tot[now]； j//状态二进制文件的最左边是最小的位，换行时的最后一定是0 a[now][j]=1； //换行时最左边的新线为0for(llj=1； j=m； j () { las=now，now^=1； memset(h，0，sizeof(h ) h )、tot[now]=0； //cout---------endl； for(llk=1； k=tot[las]； k ) { LL zt=a[las][k]，B1=(ZT(j-1 ) ) 2，B2=) ztj ) %2； //couti ' ' j ' status ' ZT ' ' B1 ' ' B2 endl； //提取关键网格上的两段轮廓线状态，zt表示前面的状态，LL num=js[las][k]； //此状态的数量if (！ MP[I][j]{if (！ b1！ b2 )//一个可能的故障状态为：原始状态下无右下插头//cout '故障' ' ZT endl ins (ZT，num )； //表示此处故障(}else if (！ b1！ b2 ) ) /对于该状态，只能选择右下状态，但可以选择的条件是右下均为空地if(MP[I1][j]MP[I][j1] ) (ins (ztrrddm [ j-- ) //插头状态j-1和j各一个//cout ' 00 ' ztrrddm [ j-1 ] rrddm [ j ] ' ' num endl； } }else if (！ b1b2) )/B1为0，但b2中存在if(MP[I][J1] ) (ins ) ZT，num )； //转至与右连接的插头//cout '01-right ' zt ' 'num endl； (if ) MP[I1][j] )/cout ' 01-botton ' ZT-rrddm [ j ] rrddm [ j-1 ] ' ' num endl； ins(ZT-rrddm[j]rrddm[j-1]，num )； //转到下面的插头}Elseif(B1！ b2 ) if(MP[I][J1] ) ins ) ZT-rrddm[J-1]rrddm[J]，num )； //左为右//cout ' 10-right ' ZT-rrddm [ j-1 ] rrddm [ j ] ' ' num endl； (if ) MP[I1][j] ) { //cout '10-botton' zt ' 'num endl； ins(ZT，num )； //下移，状态不变}}elseif(B1==1B2==1) /减少一个，也就是说两个连接块匹配了一次，如果状态有一个独立的连接块，则ins(ZT-rrddm(j-1) ) } } } }}char s1[1000]； int main ()//Freopen(in.txt )、(r )、stdin )； //Freopen(out1.txt )、(w )、stdout )； Len1、len2、len3； lt，I，j； scanf('%lld '，t )； LL num=0； rrddm[0]=1； for(I=1； i=14； I ) rrddm(I )=rrddm (I-1 ) 1； while(t---- ) { num； 扫描(' % lld % lld )、n、m )； now=0； for(I=1； i=n； I ) for(j=1； j=m； j ) scanf('%lld '，mp[i][j]； } }工作()； LL res=0； for(llk=1； k=tot[now]； k({LLZT=a[now][k]； if(ZT==0) res=js[now][k]； } printf (case % lld : there are % lldwaystoeatthetrees. n '，num，res )； }返回0； }