POJ 1038 Bugs Integrated, Inc. 三进制状态压缩DP

Bugs Integrated, Inc.

Time Limit: 15000MS Memory Limit: 30000K
Case Time Limit: 5000MS

Description

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.

Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
Task
You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.

Input

The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).

Output

For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

Sample Input

Sample Output

Source

题意

如图,给定一个大小为N*M的矩阵,其中M<=10,矩阵中存在一些坏点,往矩阵中放入2*3或者3*2的小方块,坏点不能被小方块覆盖,问矩阵中最多能放入多少个小方块。

思路

由于M<=10,可以使用状态三进制压缩DP,用一个三进制的数表示每一行的状态,很显然,需要写一对函数来进行状态的编码和解码。对于每一个格子对应三进制的每一位:如果这一位是0,表示这个格子被占用;如果这一位是1,表示这个格子未被占用,但是他上方的格子被占用;如果这一位是2,表示这一个格子和他上方的一个格子都没被占用。当获取到上一排的一个有效状态的时候,通过dfs生成若干个这一排的有效状态,假设上一排的状态用last数组表示,这一排的状态用now数组表示,考虑这一排每一个位置pos小方块的放法:首先,如果这个格子是坏点,那么只能强行标记为已经占用的状态now[pos]=0,dfs后直接返回;如果考虑横着放,则需要now[pos-2]=2且now[pos-1]=2且last[pos]>=1,将now数组相关位置设置为0后再进行dfs,注意dfs返回后,要将now数组还原;如果考虑竖着放,则需要保证now[pos-1]=2且last[pos-1]=2且last[pos]=2,进行dfs也同样需要对now数组进行置位或还原;然后开可以考虑不放的情况,将now[pos]设置为min(2,last[pos]+1)即可。dfs的同时,还需要记录新添加的小方块的个数。当dfs到达边界的时候,进行dp的转移。