2020-05-25 00:40:07

### 题目大意

$1\leq W,H \leq 60$

### 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

### 乱搞做法

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是对称的，略

• star
首页