奇妙题目的奇妙乱搞(详细揭秘)

前几天vp subregional看到这样一个题，写了写发现和正解不一样，也不会证自己的做法的正确性 **有没有路过的好心人帮忙证明一下这个乱搞做法正确性或错误性（？** ### 题目大意 给一个 $W\times H$ 的矩形，划分成尽量少的整边长正方形，输出方案 $1\leq W,H \leq 60$ ### 错误做法 猜想一定存在一条分割线贯穿矩形，使得矩形分成两半，并且两半的最优解拼起来就是整个矩形的最优解，然后随便dp ### Hack ``` AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB AAAAAAAABBBBBBBBBBB AAAAAAAAABBBBBBBBBB BBBBBCCCBBBBBBBBBBB vs AAAAAAAAABBBBBBBBBB BBBBBCCCBBBBBBBBBBB CCCCCCCCCBBBBBBBBBB BBBBBCCCBBBBBBBBBBB CCCCCCCCCAAAAAAAACC BBBBBAAAAAAACCCCCCC CCCCCCCCCAAAAAAAACC BBBBBAAAAAAACCCCCCC CCCCCCCCCAAAAAAAABB CCCCCAAAAAAACCCCCCC CCCCCCCCCAAAAAAAABB CCCCCAAAAAAACCCCCCC CCCCCCCCCAAAAAAAACC CCCCCAAAAAAACCCCCCC CCCCCCCCCAAAAAAAACC CCCCCAAAAAAACCCCCCC CCCCCCCCCAAAAAAAABB CCCCCAAAAAAACCCCCCC CCCCCCCCCAAAAAAAABB total=7 total=8 ``` 这两个平面图的色数都是3，很有趣（被打 ### 乱搞做法 根据以上反例猜想dp的每一个状态要么是一个矩形，要么是一个矩形抠掉一个角上的另一个矩形（称为L形） 矩形状态枚举抠掉哪个正方形转移，共$O(n)$种转移，$O(n^2)$种状态 L形状态共有5对关于$y=x$对称的转移共10种，共$O(1)$种转移，$O(n^4)$种状态 **1.贴小矩形的右边界** （`X`是抠掉的位置，`O`是新放置的正方形，下同） ``` XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... OOOO..... OOOO..... OOOO..... OOOO..... ......... ......... ``` **2.贴大矩形的左边界，右边界不到小矩形右边界** ``` XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... OOO...... OOO...... OOO...... ``` **3.贴大矩形的左边界，同时右边界贴小矩形右边界** ``` XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... OOOO..... OOOO..... OOOO..... OOOO..... ``` **4.贴大矩形的左边界，右边界超出小矩形右边界** ``` XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... OOOOO.... OOOOO.... OOOOO.... OOOOO.... OOOOO.... ``` （此时转移到整个矩形上下翻转后的情况） **5.贴大矩形的左边界，同时右边界贴大矩形右边界** ``` XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... XXXX..... OOOOOOOOO OOOOOOOOO OOOOOOOOO OOOOOOOOO OOOOOOOOO OOOOOOOOO OOOOOOOOO OOOOOOOOO OOOOOOOOO ``` **6~10是对称的，略** 可以发现每种情况要么大矩形边界缩小，要么小矩形边界扩大，所以可以 $O(n^4)$ dp ### std 看不懂俄文，机翻了一下好像是说什么枚举杨表然后本地打表，反正看起来就不怎么多项式