状态压缩dp

1100ms左右 比优化版略慢

y总讲的f[i][j]感觉不好理解，比如f[m][0]是结果，而m列前一列并不需要没有伸出来到最后一列
把j看成当前列伸到下一列的状态就好理解了，代码是一样的，有时间详细写下

import java.io.*;
import java.util.*;

class Main {

    //存储状态合法性
    static int kinds;
    static boolean[] flag = new boolean[4096];

    static long[][] f = new long[12][4096];

    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            if (n == 0 && m == 0) break;

            label:
            for (int k = 0; k < 1<<n; k++) {
                int cnt = 0;
                flag[k] = true;
                //每个状态一定是n位二进制表示
                for (int t = 0; t < n; t++) {
                    int x = k >> t;
                    if ((x&1) == 1) {
                        if ((cnt&1) == 1) {
                            flag[k] = false;
                            //已经出现连续奇数个1了，检查下个状态
                            continue label;
                        } else cnt = 0;
                    } else cnt++;
                }
                if ((cnt&1) == 1) flag[k] = false;
            }

            //关键，每次都要重新初始化f数组，否则会因之前的状态影响结果
            //因为i表示的是列数，所以f数组使用到了1~m行
            for (int i = 0; i <= m; i++) Arrays.fill(f[i], 0);
            //从第零列只能伸出0个
            f[0][0] = 1;

            for (int i = 1; i<= m; i++)
                for (int j = 0; j < 1<<n; j++)
                    for (int k = 0; k < 1<<n; k++)
                        if ((j&k) == 0 && flag[j|k]) f[i][j] += f[i-1][k];
            out.write(f[m][0]+"\n");
        }

        br.close();
        isr.close();

        out.flush();
        out.close();
        osw.close();
    }
}

优化

800ms 左右

import java.io.*;
import java.util.*;

class Main {

    //存储状态合法性
    static int kinds;
    static boolean[] flag = new boolean[4096];

    static long[][] f = new long[12][4096];

    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            if (n == 0 && m == 0) break;

            label:
            for (int k = 0; k < 1<<n; k++) {
                int cnt = 0;
                flag[k] = true;
                //每个状态一定是n位二进制表示
                for (int t = 0; t < n; t++) {
                    int x = k >> t;
                    if ((x&1) == 1) {
                        if ((cnt&1) == 1) {
                            flag[k] = false;
                            //已经出现连续奇数个1了，检查下个状态
                            continue label;
                        } else cnt = 0;
                    } else cnt++;
                }
                if ((cnt&1) == 1) flag[k] = false;
            }

            //存储每种合法状态的前一种状态
            Map<Integer, List<Integer>> pres = new HashMap<>();

            for (int k = 0; k < 1 << n; k++) {
                //此处不能过滤，因为p | k才是列状态
                //if (!flag[k]) continue;
                for (int p = 0; p < 1 << n; p++)
                    if ((p & k) == 0 && flag[p | k]) {
                        if ( pres.get(k) != null)  pres.get(k).add(p);
                        else {
                            List<Integer> list = new ArrayList<>();
                            list.add(p);
                            pres.put(k, list);
                        }
                    }
            }

            //关键，每次都要重新初始化f数组，否则会因之前的状态影响结果
            //因为i表示的是列数，所以f数组使用到了1~m行
            for (int i = 0; i <= m; i++) Arrays.fill(f[i], 0);
            //从第零列只能伸出0个
            f[0][0] = 1;

            for (int i = 1; i<= m; i++)
                for (int j = 0; j < 1<<n; j++) {
                    List<Integer> list = pres.get(j);
                    if (list == null) continue;
                    for (int x : list) f[i][j] += f[i - 1][x];
                }
            out.write(f[m][0]+"\n");
        }

        br.close();
        isr.close();

        out.flush();
        out.close();
        osw.close();
    }
}