SZY-猪头dp探析.ppt

插头dp吉大附中实验学校 宋;1.棋盘覆盖问题;uva 11270n×m 的;if(nm)swap(n,m;目前的格子状压记录每一位为0（;红色表示格子状态不填向上填向左;填时必须保证方案合法不能使位置;2.简单回路问题;Formula 1 一个 m ;Formula 1 (Ural;基本概念插头一个格子某个方向的;基本概念轮廓线已决策格子和未决;考虑逐格递推状态：f[i][j;考虑逐格递推状态：f[i][j;将联通的插头用相同数字表示;将联通的插头用相同数字表示一种;将联通的插头用相同数字表示一种;确立状态最小表示法12201f;我们再来看对于这道题的特殊性质;我们再来看对于这道题的特殊性质;题目性质每个非障碍格子恰好有2;进一步分析从左到右一定不会出现;插头不会交叉插头两两匹配括号序;括号表示法(()))(0：无插;有人会去用三进制么？用两位字节;Case 1产生新的联通分量原;Case 1对应一种情况：;Case 2 ( 插头(插头#;Case 2另两种情况与例子类;Case 2ji删除i，j在当;Case 2由括号匹配的性质，;Case 2由括号匹配的性质，;Case 3维持联通分量 ) ;Case 3对应四种情况：不会;实现：宽搜出所有状态每次寻找当;最小表示法可做参考 hdu 1;3.棋盘染色问题;black and white;n=2,m=3时的九种情况;状态表示：显然需要记录轮廓线上;状态表示：显然需要记录轮廓线上;状态表示：显然需要记录轮廓线上;对于格子的联通情况，此时连通的;不过仍有性质两个联通块不会交叉;不过仍有性质两个联通块不会交叉;122321(#(###()#;只做介绍，不推荐使用，代码过于;严重的健康警告：对于擅自使用广;下面考虑转移：考虑涂色为白色或;下面考虑转移：考虑涂色为白色或;下面考虑转移：考虑涂色为白色或;上方联通分量退出轮廓线;上方联通分量退出轮廓线左侧联通;实现：最小表示法用long l;实现：最小表示法用long l;for(所有格子){ cur^;4.非棋盘类问题;[NOI2007]生成树计数给;分析题目，n很大且k很小当前状;状态为：设f[i][j]表示现;状态为：设f[i][j]表示现;转移时枚举第i个点和前面哪些点;无标题;无标题;我们可以处理出转移矩阵，用矩乘;题目列表1.Uva 11270;无标题