没题解来水一发

三进制状压,对于每一行的一个格子有以下状态：
0：当前格子没铺或者铺了一个格子(按行转移 这格铺不铺不影响下一行 因此可以当成一种状态)
1：当前格子以及相邻的下面一个格子都铺了
2：当前格子以及相邻的下面两个格子都铺了

因为无效状态较多 因此不枚举而是用搜索进行转移比较好

评级是简单就特么离谱

（另外 感谢acw的数据帮我节省了debug的时间 在poj上一直wa于是来到了这里）

Java 代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int row, col, len = 59049 + 1, dp[] = new int[len], ndp[] = new int[len];
    static int mat[][] = new int[155][15], caseId;
    static int oldState[] = new int[10], newState[] = new int[10];

    public static void main(String[] args) {
        int n = IN.nextInt();
        while (n-- > 0) {
            ++caseId;
            row = IN.nextInt() + 1;
            col = IN.nextInt();
            int m = IN.nextInt();
            for (int i = 0; i < m; i++) {
                mat[IN.nextInt()][IN.nextInt() - 1] = caseId;
            }
            solve();
        }
    }

    final static int INF = -10000;
    static int res, hi, t;

    private static void solve() {
        Arrays.fill(dp, INF);
        dp[0] = 0;
        res = 0;
        t = 1;
        for (int i = 1; i < row - 1; i++) {
            Arrays.fill(ndp, INF);
            hi = t;
            t = 1;
            for (int j = 0; j < hi; j++) {
                if (dp[j] >= 0) {
                    decode(j);
                    trans(j, i, 0, 0);
                }
            }
            System.arraycopy(ndp, 0, dp, 0, t);
        }
        System.out.println(res);
    }

    public static void trans(int state, int r, int c, int cnt) {
        if (c == col) {
            int nstate = encode(newState);
            t = Math.max(nstate + 1, t);
            ndp[nstate] = Math.max(ndp[nstate], dp[state] + cnt);
            if (r == row - 2) {
                res = Math.max(res, ndp[nstate]);
            }
            return;
        }
        if (check1(r, c) && oldState[c] == 0 && oldState[c + 1] == 0 && oldState[c + 2] == 0) {
            newState[c] = newState[c + 1] = newState[c + 2] = 1;
            trans(state, r, c + 3, cnt + 1);
            newState[c] = newState[c + 1] = newState[c + 2] = 0;
        }
        if (check2(r, c) && oldState[c] == 0 && oldState[c + 1] == 0) {
            newState[c] = newState[c + 1] = 2;
            trans(state, r, c + 2, cnt + 1);
            newState[c] = newState[c + 1] = 0;
        }
        newState[c] = oldState[c] == 2 ? 1 : 0;
        trans(state, r, c + 1, cnt);
    }

    final static int pow[] = new int[] { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 };

    public static int encode(int A[]) {
        int ret = 0;
        for (int i = 0; i < col; i++) {
            ret += A[i] * pow[i];
        }
        return ret;
    }

    public static void decode(int A) {
        for (int i = 0; i < col; i++) {
            oldState[i] = A % 3;
            A /= 3;
        }
    }

    private static boolean check1(int x, int y) {
        int nx, ny;
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 2; j++) {
                nx = x + i;
                ny = y + j;
                if (nx >= row || ny >= col || mat[nx][ny] == caseId) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean check2(int x, int y) {
        int nx, ny;
        for (int i = 0; i <= 2; i++) {
            for (int j = 0; j <= 1; j++) {
                nx = x + i;
                ny = y + j;
                if (nx >= row || ny >= col || mat[nx][ny] == caseId) {
                    return false;
                }
            }
        }
        return true;
    }

    static class IN {

        private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 65535);
        private static StringTokenizer st = null;

        public static String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    break;
                }
            }
            return st.nextToken();
        }

        public static int nextInt() {
            return Integer.valueOf(next());
        }
    }
}