一行有20个格子，直接dp肯定挂，注意T<=20 可以推断出行和列的最大间距的最小值min(max(row),max(col))==5,于是对行和列分别做一次dp, 限制间距不超过5就行了

一行状态最多 598，不算上T 的话

不过这个方法有点慢了，虽然没有做优化。。。。

• Re:AC了，基于连通性状压dp搞的 (204) Los_Angelos_Laycurse 2014-03-11 22:03:04
  • 最大间距一定要设置成5才能AC，为什么呢？我用(T+3)/4不行。 (56) yygy 2014-06-30 19:46:15
    • Re:最大间距一定要设置成5才能AC，为什么呢？我用(T+3)/4不行。 (30) JiaJunpeng 2014-06-30 20:43:45
• Re:AC了，基于连通性状压dp搞的 (193) Los_Angelos_Laycurse 2014-03-11 22:13:32
• 我第一眼看这题也感觉是插头DP，但是，20*20的格子不会状态太多吗？ (154) yygy 2014-06-29 21:46:46
• 哦你是说这个选出来 的格子左右距离还有上下距离的的最小值是<=4/T然后我们拿小的一维压缩是吗？ (154) yygy 2014-06-29 21:52:49
• 然后枚举行的范围做一下，再枚举列的范围做一下。这样比起直接搞状态是减少了很多。 (154) yygy 2014-06-29 21:54:03
  • 为什么DZX大牛说这题是搜索。 (0) yygy 2014-06-30 20:03:22
    • Re:为什么DZX大牛说这题是搜索。 (26) JiaJunpeng 2014-06-30 20:40:58
      • 最大间距为什么一定要设置成5才能AC，不理解啊。 (30) yygy 2014-06-30 21:17:18
        • Re:最大间距为什么一定要设置成5才能AC，不理解啊。 (70) JiaJunpeng 2014-06-30 22:45:41
          • 我是想对于T=20那个间距定5，如果T=16，定为4可以吗？ (76) yygy 2014-06-30 22:48:55
            • Re:我是想对于T=20那个间距定5，如果T=16，定为4可以吗？ (41) Los_Angelos_Laycurse 2014-06-30 22:54:05
              • 难道是我的算法写得有问题？你试试我下面这组数据 (54) yygy 2014-07-01 08:17:57
                • 你是直接用状态下标来DP的吗？我是用状态扩展来DP，这样可以减少很多无效状态，所以我的速度很快。 (70) yygy 2014-07-01 08:19:38
                • Re:难道是我的算法写得有问题？你试试我下面这组数据 (83) JiaJunpeng 2014-07-01 08:55:19
                  • Re:难道是我的算法写得有问题？你试试我下面这组数据 (57) JiaJunpeng 2014-07-01 08:57:18
                    • 贾兄现在是本科生还是研究生啊？这么早就起来啦。 (44) yygy 2014-07-01 08:58:11