教学管理信息服务平台,优化大师,流量套餐汇总网站,深圳招聘信息最新招聘2021文章目录 状态压缩DP例题列表棋盘式1064. 小国王⭐#x1f402;#xff08;好题#xff01;#xff09;做题套路总结 327. 玉米田#xff08;好题#xff01;#x1f402; 和1064. 小国王差不多的题目#xff09;292. 炮兵阵地#xff08;和上面两道题差不多#xff… 文章目录 状态压缩DP例题列表棋盘式1064. 小国王⭐好题做题套路总结 327. 玉米田好题 和1064. 小国王差不多的题目292. 炮兵阵地和上面两道题差不多需要多考虑上上一行 集合524. 愤怒的小鸟TODO529. 宝藏TODO 相关链接 状态压缩DP
状压 DP 是动态规划的一种通过将状态压缩为整数来达到优化转移的目的。 更多介绍可见相关链接 部分。
例题列表
棋盘式
1064. 小国王⭐好题
https://www.acwing.com/activity/content/problem/content/1292/ 洛谷相同题目链接P1896 [SCOI2005] 互不侵犯
每个国王会攻击周围一圈儿。
每一层只需要考虑上一层的状态就可以了。 dp数组定义long[][][] dp new long[N][K][M]; 第i行已经放了j个国王当前行的国王集合为a此时的方案数。
枚举顺序见代码。
import java.io.BufferedInputStream;
import java.util.*;public class Main {final static int N 12, M 1 10, K 110; // 可以开大一点无所谓static int n, m;static ListInteger state new ArrayList(); // 里面存放的是在一行中没有冲突的集合static int[] cnt new int[M];static ListInteger[] head new ArrayList[M]; // 里面存放的是每一种状态相邻的行可以放置哪些状态static long[][][] dp new long[N][K][M];static {Arrays.setAll(head, e - new ArrayList());}public static void main(String[] args) {Scanner sin new Scanner(new BufferedInputStream(System.in));n sin.nextInt();m sin.nextInt();// 预先处理出所有可选的状态集合即在一行内没有冲突的集合,以及这种状态的行中有几个国王for (int i 0; i 1 n; i) {if (check(i)) {state.add(i);cnt[i] count(i);}}// 预先处理每一行之后 相邻的行可以放置哪种状态集合for (int i 0; i state.size(); i) {for (int j 0; j state.size(); j) {int a state.get(i), b state.get(j);// 如果没有冲突// 没有列上一样的也没有列上相邻的if ((a b) 0 check(a | b)) {head[i].add(j);}}}// 第i行已经放了j个国王当前行的国王集合为adp[0][0][0] 1;// 枚举每一行for (int i 1; i n 1; i) {// 枚举已经选了m个国王需要从0枚举到mfor (int j 0; j m; j) {// 枚举每一种状态作为当前行不管是不是合法的无所谓因为不合法的对应的head[a]里面是空的for (int a 0; a state.size(); a) {// 枚举a后面可以跟着的每一种bfor (int b: head[a]) {int c cnt[state.get(a)];// 如果当前已经选择的国王数量当前行的国王数量if (j c) {dp[i][j][a] dp[i - 1][j - c][b];}}}}}System.out.println(dp[n 1][m][0]);}// 检查一个状态集合是否在这一行内有冲突static boolean check(int state) {for (int i 0; i n; i) {// 如果连续两列都为1表示有冲突if (((state i 1) 1 (state i 1 1) 1)) return false;}return true;}// 计算这个状态集合中摆放了几个国王static int count(int state) {int res 0;for (int i 0; i n; i) res state i 1;return res;}
}做题套路总结
最后来总结一下写法
先预先处理出所有在一行中没有冲突的列集合然后对计算出对所有合理列集合 来说 没有冲突的列集合最后 枚举行、当前行的列状态、上一行的列状态计算状态转移
327. 玉米田好题 和1064. 小国王差不多的题目
https://www.acwing.com/problem/content/329/ 跟上一题相比有一些变化
冲突的范围从周围一圈变成十字的形状部分格子是无法放置玉米的种植玉米的数量是没有限制的
import java.io.BufferedInputStream;
import java.util.*;public class Main {final static int N 14;final static long MOD (long)1e8;static int m, n;static int[] land new int[N]; // 记录每一行中的哪些列是不能种植的static ListInteger states new ArrayList(); // 记录所有在一行中合法的状态static ListInteger[] head new ArrayList[1 N];static {Arrays.setAll(head, e - new ArrayList());}public static void main(String[] args) {Scanner sin new Scanner(new BufferedInputStream(System.in));m sin.nextInt();n sin.nextInt();for (int i 1; i m; i) {for (int j 0; j n; j) {int t sin.nextInt();land[i] (t ^ 1) j; // 0表示不育}}// 预先处理出在一行中合法的所有状态加入states中for (int i 0; i 1 n; i) {if (check(i)) states.add(i);}// 预先处理出哪两种行可以放在一起for (int i 0; i states.size(); i) {for (int j 0; j states.size(); j) {int a states.get(i), b states.get(j);// 只要这两行在列上没有重复就可以放在一起if ((a b) 0) {head[i].add(j);}}}long[][] dp new long[m 2][states.size() 1];dp[0][0] 1; // dp数组初始化// 枚举每一行for (int i 1; i m 1; i) {// 枚举该行的状态for (int j 0; j states.size(); j) {if ((states.get(j) land[i]) 0) {// 枚举可以从这种行转移过来的行for (int k: head[j]) {dp[i][j] (dp[i][j] dp[i - 1][k]) % MOD;}}}}System.out.println(dp[m 1][0]);}static boolean check(int state) {for (int i 0; i n - 1; i) {// 检查是否有连续两位都是1的情况if ((state i 1) 1 ((state i 1 1) 1)) return false;}return true;}
}Q为什么 dp[][] 数组初始化时只 设置 dp[0][0] 1而不把 所有 dp[0][j] 1 Adp[0][0] 1表示在还没有种植任何玉米的状态下也就是前0行这种情况只有1种。而dp[0][j] (j ! 0)的含义是在还没有种植任何玉米的状态下最后一行也就是不存在的这一行的种植状态是states[j]的种植方式数量这显然是不可能的所以dp[0][j] (j ! 0)都应该为0。
292. 炮兵阵地和上面两道题差不多需要多考虑上上一行
https://www.acwing.com/problem/content/294/ 跟上面两道题目相比多考虑上上一行就好了。 dp 递推的过程也 多写一层循环。
import java.io.BufferedInputStream;
import java.util.*;public class Main {final static int N 105, M 11;static int n, m;static int[] land new int[N], cnt new int[1 M]; // 记录每一行不能放置炮兵的列集合static ListInteger states new ArrayList(); // 记录所有在一行中合理的列集合static ListInteger[] head new ArrayList[1 M];static {Arrays.setAll(head, e - new ArrayList());}public static void main(String[] args) {Scanner sin new Scanner(new BufferedInputStream(System.in));n sin.nextInt();m sin.nextInt();// 记录每一行不能被放置的列集合for (int i 1; i n; i) {String s sin.next();for (int j 0; j m; j) {land[i] (s.charAt(j) H? 1: 0) j;}}// 计算出所有在一行中合理的列集合for (int j 0; j 1 m; j) {if (check(j)) {states.add(j);cnt[j] count(j);}}// 计算出各个集合可以和哪些集合相邻int l states.size();for (int i 0; i l; i) {for (int j 0; j l; j) {if ((states.get(i) states.get(j)) 0) {head[i].add(j);}}}int[][][] dp new int[n 1][l][l];// 枚举每一行for (int r 1; r n; r) {// 枚举当前的每个集合for (int i 0; i l; i) {if ((states.get(i) land[r]) 0) {// 枚举上一个集合for (int j: head[i]) {// 枚举上上个集合for (int k: head[j]) {if ((states.get(i) states.get(k)) 0) {dp[r][j][i] Math.max(dp[r - 1][k][j] cnt[states.get(i)], dp[r][j][i]);}}}}}}int ans 0;for (int i 0; i l; i) {for (int j 0; j l; j) {ans Math.max(ans, dp[n][i][j]);}}System.out.println(ans);}private static boolean check(int state) {for (int i 0; i m; i) { // 这里最好写成 i m写成 i m - 2 时答案就不对了// 邻近两个范围内不能有炮兵if ((state i 1) 1 ((state i 1 1) 1 || (state i 2 1) 1)) return false;}return true;}// 计算这种集合中有多少个炮兵static int count(int state) {int res 0;for (int i 0; i m; i) res state i 1;return res;}
}集合
524. 愤怒的小鸟TODO
https://www.acwing.com/problem/content/526/ 数据范围
在这里插入代码片529. 宝藏TODO
https://www.acwing.com/problem/content/531/
在这里插入代码片相关链接
从集合论到位运算——常见位运算技巧及相关习题 状态压缩DP 【力扣周赛】第 355 场周赛构造二分答案异或前缀 状态压缩⭐ 【算法基础动态规划】5.4 状态压缩DP
