典型状压dp
- LeetCode

典型状压dp

普通状态压缩dp求方案数玉米田

带个数限制的状态压缩dp求方案数小国王

多行渗透的状态压缩求最大放置个数炮兵阵地

import java.io.*;
public class Main{
    static int[][][] f = new int[2][1 << 12][1 << 12]; 
    static int m, n;
    static int[] w;
    static ArrayList<Integer> state = new ArrayList<Integer>();
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        m = scan.nextInt(); n = scan.nextInt();
        w = new int[m + 3];
        String tmp;
        for (int i = 1; i <= m; i ++){
            tmp = scan.next();
            for (int j = 0; j < n; j ++){
                if (tmp.charAt(j) == 'H')
                    w[i] += (1 << (n - 1 - j));
            }
        }
        for (int i = 0; i < 1 << n; i ++){
            if (check(i) == true) state.add(i);
        }
        //三层，用head只能保证两层的关系
        for (int i = 1; i <= m + 2; i ++){
            for (Integer j : state){
                if ((w[i] & j)!= 0)continue;
                for (Integer k : state){
                    for (Integer p : state){
                        if ((j & k | k & p | p & j) == 0)
                            f[i & 1][j][k] = Math.max(f[i & 1][j][k], f[i - 1 & 1][k][p] + count(j)); 
                    }
                }
            }
           // System.out.println("第" + i + "行:" + f[i][0][0]); 
        }
        System.out.println(f[m + 2 & 1][0][0]);
    }
    public static boolean check(int k){
        for (int i = 0; i < n; i ++){
            if ((k >> i & 1) == 1 && ( (k >> (i + 1) & 1) == 1 || (k >> (i + 2) & 1) == 1 ) ) return false;
        }
        return true;
    }
    public static int count(int k){
        int res = 0;
        for (int i = 0; i < n; i ++)
            res += (k >> i & 1) ;
        return res;
    }
}

愤怒的小鸟（难度较大）

蒙德里安的梦想

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

//state 定义的是从i-1列伸到i列的状态，因此要计算
public class Main{
    static int n, m, T;
    static int[][]f = new int[15][1 << 15];
    static ArrayList<Integer> state = new ArrayList<Integer>();
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        while (true){
            state.clear();
            m = scan.nextInt(); n = scan.nextInt();
            for (int i = 0; i < m; i ++)
                Arrays.fill(f[i], 0);
            if (n == 0 && m == 0) break;
            int cnt = 0;
            for (int i = 0; i < 1 << m; i ++){
                boolean flag = true; cnt = 0;
                for (int j = 0; j < m; j ++){
                    if ((i >> j & 1) == 1){
                        if (cnt % 2 == 1){
                            cnt = 0;
                            flag = false;
                        }
                    }else
                        cnt++;
                }
                if (cnt % 2 == 1)flag = false;
                if (flag == true) state.add(i);
            }    
            /*for (Integer s : state)
                System.out.print(s + " ");
            System.out.println();  */
            f[1][0] = 1;
            for (int i = 1; i <= n + 1; i ++){
                for (Integer s : state){
                    for (Integer k : state){
                        if ((s & k) == 1)continue;
                        f[i][s] += f[i - 1][k];
                    }
                }
            }
            System.out.println(f[n + 1][0]);
        }
    }
}

状态压缩dp

典型状压dp

LeetCode