I think it is easy to provide the answer is ⌊(H+1)*(W+1)/6⌋ but my english is pool.XD So I can only provide it in Chinese. I'm so sorry for my pool English. Hope somebody can translate it to English. 问题等价于在(H+1)*(W+1)的格子中放置2*3的砖块，砖块可以旋转，两个砖块之间不能重合但是可以共用边或顶点，求最多能放多少砖块。 考虑X*Y的格子中能放多少砖块 <1>当1<X，Y<=7时，答案为⌊X*Y/6⌋。这可以通过暴力验证 <2>当X=6且Y>1时，砖块可以填满格子。原因是6*2和6*3的格子都可以被砖块填满，而任何大于1的数都可以表示为2*i+3*j，其中i和j为自然数。 <3>由<2>可以推出，当X为6的倍数且Y>1时，砖块可以填满格子。所以接下来只需考虑X和Y都不是6的倍数的情况。 <4>当1<X<6且Y>6时，分以下两种情况： 如果Y%6==1，那么将Y表示为6*c+7。X*Y就被分为两个部分：X*(6*c)、X*7。根据<3>可知第一部分会被砖块填满，又因为1<X<6可根据<1>得出后一部分答案为⌊X*7/6⌋，所以总体答案为⌊X*Y/6⌋。 如果Y%6!=1，那么将Y表示为6*c+d，其中d=Y%6。X*Y就被分为两个部分：X*(6*c)、X*d。根据<3>可知第一部分会被砖块填满，又因为1<X<6且1<d<6可根据<1>得出后一部分答案为⌊X*d/6⌋，所以总体答案为⌊X*Y/6⌋。 <5>当6<X，Y时，分以下三种情况 如果X%6==1且Y%6==1，那么将X表示为6*a+7，将Y表示为6*c+7。X*Y就被分为四个部分：(6*a)*(6*c)、(6*a)*7、7*(6*c)、7*7。根据<3>可知前三个部分会被填满，根据<1>可知第四个部分答案为⌊7*7/6⌋，所以总体答案为⌊X*Y/6⌋。 如果X%6和Y%6中仅有一个为1，不失一般性地我们可以设X%6==1，那么将X表示为6*a+7，将Y表示为6*c+d，其中d=Y%6。X*Y就被分为四个部分：(6*a)*(6*c)、(6*a)*d、7*(6*c)、7*d。根据<3>可知前三个部分会被填满，根据<1>可知第四个部分答案为⌊7*d/6⌋，所以总体答案为⌊X*Y/6⌋。 如果X%6!=1且Y%6!=1，那么将X表示为6*a+b，将Y表示为6*c+d，其中b=X%6,d=Y%6。X*Y就被分为四个部分：(6*a)*(6*c)、(6*a)*d、b*(6*c)、b*d。根据<3>可知前三个部分会被填满，又因为1<b，d<6，根据<1>可知第四个部分答案为⌊b*d/6⌋，所以总体答案为⌊X*Y/6⌋。