插头DP 专题训练 动态规划

插头DP 专题训练

做了接近一天插头DP,感觉大体上比较理解了。 首先,这玩意主要是处理棋盘上路径/回路的计数或是最值查询,数据范围的特点是列数比较小(大概在10左右),行数可以稍多一些,有时候数据不保证行数大于列数,需要对矩阵进行旋转后再做。 主要是引入了插头的概念,DP时逐格转移,并状压轮廓线上m+1个插头的状态(···