%%%%orz苏大佬 虽然苏大佬的baff吸不得，苏大佬的梦信不得，但是膜苏大佬是少不得的囧
这题还是比较有收获的 哼居然有我不会做的插头DP
自己yy了下，2表示属于2的插头，3表示3的插头
假如当前是0点，并且没有左上连向，那么可以不放插头，也可以放2放3，否则就是常规操作
假如是障碍那就不能有插头
然后假如是2和3点，就可以放个单插头，或者直接继承前面的插头
我觉得很OK啊。。。然后就不会记录ans了
？？？？黑人问号啊，怎么判是否结束了啊
写了各种异或判断是否当前状态把四个位置都放了，然后。。就只能过这个↓
2 3
2 2 0
0 3 3
直接去%苏大佬的code，发现她是这么写的：
ans=0; work(); for(int i=1;i<=dp[now].size;i++) { ans+=dp[now].num[i];//将所有可行的方案加入ans } printf("%lld ",ans>0?ans-2:0);
她怎么能直接把状态的最小值累加啊？？？
调试了一下发现，这个栈里面的元素要么只有一个要么没有要你这个for何用啊
彻底懵逼。。直接去膜拜 终于懂了
是因为到最后肯定只有一个状态，就是0（也就是匹配完成），假如不匹配完成那么就不会成功继承。
那我现在的感觉是其他题是不是也一样？假如我让它不合法就不继承好像可以一样做欸
upd：我在做下一题的时候发现我好像沙茶了，因为每道题情况不一样，对于这题而言，它不需要形成回路，并且可以有空格不行经，使得它在转移的时候可以空转移，所以能够无需特判直接转移到末尾
整理下思路，一开始我想的是分开算2和3的长度，这个很难实现，因为它们不相交所以我只需要求放了插头的位置数就行了，对于继承答案可以直接转移到最后一个位置，中途继承判合法就行了
为什么每次写s=set_bracket(s,j,q);都特别想笑。。。我也想把LCT改成YZH
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const LL mod=100037; int n,m; int mp[20][20]; struct node { LL mn[110000]; int top;LL hash[110000],sta[110000]; void pha(int s,LL mmin) { int x=s%mod; while(hash[x]!=0&&sta[hash[x]]!=s)x=(x+1)%mod; if(hash[x]==0)sta[++top]=s,hash[x]=top; mn[hash[x]]=min(mn[hash[x]],mmin); } void clean() { top=0; memset(mn,63,sizeof(mn)); memset(hash,0,sizeof(hash)); } }dp[2]; LL get_bracket(LL s,LL p) { return (s>>((p-1)*2))&3; } LL set_bracket(LL s,LL p,LL v) { s^=(get_bracket(s,p)<<((p-1)*2)); s^=(v<<((p-1)*2)); return s; } int pre,now; void Plug_DP() { pre=0,now=1; dp[now].clean();dp[now].pha(0,0); for(LL i=1;i<=n;i++) { for(LL j=1;j<=m;j++) { swap(pre,now);dp[now].clean(); for(int k=1;k<=dp[pre].top;k++) { LL s=dp[pre].sta[k],mn=dp[pre].mn[k]; LL p=get_bracket(s,j),q=get_bracket(s,j+1); if(mp[i][j]==0) { if(p==0&&q==0)dp[now].pha(s,mn); } else if(mp[i][j]==1) { if(p==0&&q==0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,0); dp[now].pha(s,mn); if(mp[i][j+1]!=0&&mp[i+1][j]!=0) { s=set_bracket(s,j,2); s=set_bracket(s,j+1,2); dp[now].pha(s,mn+1); s=set_bracket(s,j,3); s=set_bracket(s,j+1,3); dp[now].pha(s,mn+1); } } else if(p==0&&q>0) { if(mp[i+1][j]!=0) { s=set_bracket(s,j,q); s=set_bracket(s,j+1,0); dp[now].pha(s,mn+1); } if(mp[i][j+1]!=0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,q); dp[now].pha(s,mn+1); } } else if(p>0&&q==0) { if(mp[i+1][j]!=0) { s=set_bracket(s,j,p); s=set_bracket(s,j+1,0); dp[now].pha(s,mn+1); } if(mp[i][j+1]!=0) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,p); dp[now].pha(s,mn+1); } } else if(p>0&&q>0) { if(p==q) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,0); dp[now].pha(s,mn+1); } } } else { if(p==0&&q==0) { if(mp[i][j+1]==1||mp[i][j+1]==mp[i][j]) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,mp[i][j]); dp[now].pha(s,mn+1); } if(mp[i+1][j]==1||mp[i+1][j]==mp[i][j]) { s=set_bracket(s,j,mp[i][j]); s=set_bracket(s,j+1,0); dp[now].pha(s,mn+1); } } if((p==0&&q==mp[i][j])||(p==mp[i][j]&&q==0)) { s=set_bracket(s,j,0); s=set_bracket(s,j+1,0); dp[now].pha(s,mn+1); } } } } for(int k=1;k<=dp[now].top;k++) dp[now].sta[k]<<=2; } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&mp[i][j]); if(mp[i][j]==0||mp[i][j]==1)mp[i][j]^=1; } } Plug_DP(); printf("%lld ",(dp[now].top==0)?0:(dp[now].mn[1]-2)); } return 0; }