引例、
例1、
例2、
例3、
例4、POJ2411:Mondriaan's Dream 多米诺骨牌完美覆盖问题
本质上还是“dp[]——下标为状态,值为方案数”的状态压缩DP
注:DP中的状态转换不一定是“公式表示”,可能是“DFS搜索出来的”,也可以是“人工列举出来的所有情况(i.e. 列数m很小的情况,如m=4)”
/* 题目大意: 给定一个n*m的方格矩形,求用1*2的小矩形完全覆盖的方案数,n <= 11,m <= 11. 解题思路: 挺经典的一类状态DP--子矩形覆盖父矩形,这类DP一般对一行的01状态进行压缩, 然后按行进行转移。 这题中每列的0表示未被覆盖,下一行的就必须覆盖它,我是理解成一个插头,留给下一行 一个插头。每列的1表示已被覆盖,或者理解成没有向下的插头。因为当前行只会受上一行影 响,所以可以一行一行进行转移,如果前一个状态能到下一个状态,那么就能转移。 设dp[i][j]表示到第i行状态为j的方案数,那么dp[i][j] += dp[i][k] (if (Ok(j->k))). 问题就变成Ok函数怎么写呢?易知0->1(上一行为0,当前行为1),那么1->?1->0肯定可以上面 无插头,下面留一个插头。1->1呢?不能单独判,必须判下一列是不是也是1->1,不是则不Ok。 */ #include <stdio.h> #include <string.h> #define MAX (1<<11) long long dp[20][MAX]; int n,m,ha[20],hb[20]; //上一行“已经”设置为状态pre,下一行能否设置为状态cur int Ok(int pre,int cur) { for (int i = 0; i < m; ++i) { int t1 = pre & (1<<i); int t2 = cur & (1<<i); //1. & 2. 主要从反面去排除不成立的情况;而不是从正面考虑成立的状态 //1. 想在i+1的这个位置(t2)放0:则i的这个位置(t1)必须为1,这样才不用去插头 if (!t1 && !t2) return 0; //2. 想在i+1的这个位置(t2)放1: // (1)i的这个位置必须是1 // (2) 如果i的这个位置是1,则i的下一个位置也一定要是1; // 如果i+1的这个位置是1,i+1的下一个位置也一定是1. if (t1 && t2) { i++; if (i == m) return 0; if ((pre&(1<<i)) == 0) return 0; if ((cur&(1<<i)) == 0) return 0; } } return 1; } int main() { int i,j,k,bigest; while (scanf("%d%d",&n,&m),n + m) { if (m > n) k = m,m = n,n = k; if (n % 2 && m % 2) { printf("0\n"); continue; } memset(dp,0,sizeof(dp)); bigest = (1<<m) - 1; dp[0][bigest] = 1; //尝试设置第1(i+1==1)行到第n(i+1==n)行 for (i = 0; i < n; ++i){ //第 i 行: s[j] //第 i+1 行:s[k] //"第 i+1 行" 只受"第 i 行"影响 for (j = 0; j <= bigest; ++j){ if (dp[i][j]){ for (k = 0; k <= bigest; ++k){ if (Ok(j,k)) dp[i+1][k] += dp[i][j]; } } } } printf("%lld\n",dp[n][bigest]); } //system("pause"); return 0; }
例5、
相关推荐
树型DP和状态压缩DP acm 树型DP和状态压缩DP acm 树型DP和状态压缩DP acm
由大师制作的状态压缩算法的入门资料为初学者介绍状态压缩DP相关算法并提供解题思路共47页,讲解到位 题题经典
树型DP和状态压缩DP+acm.ppt
状态压缩DP例题
华中科大2011状态压缩DP和树形DP,华中科大2011状态压缩DP和树形DP
状态压缩DP-Hamilton问题.pdf
动态规划概念 最长上升子序列 最长公共子序列 矩阵连乘问题 背包问题 树形DP 状态压缩DP
从网上搜到的一个PPT,讲状态压缩的,建议已经有一定DP水平的才下
经典入门 - 树型动态规划和状态压缩动态规划 什么是树型动态规划: 树本身就是一个递归的结构,所以在树上进行动态规划或者递推是在合适不过的事情。 必要条件:子树之间不可以相互干扰,如果本来是相互干扰的,...
状态图压缩入门的资料,如果谁需要,谁就下吧!
状态压缩的相关资料 适合刚刚接触dp状态压塑的菜鸟们看
题意: 给你n个人,从中选出p个球员和k个观众,第i个人作为观众产生价值ai,第i个人作为j号球员产生价值Ci,j ,求最大价值 (2≤n≤105,1≤p≤7,1≤k,p+k≤n,ai<109,ci,j<109) 输入 第1行输入n p k ...
基础算法 —— 代码模板链接 常用代码模板1——基础算法 排序 二分 高精度 前缀和与差分 双指针算法 位运算 离散化 区间合并 数据结构 —— 代码模板链接 常用代码模板2——数据...状态压缩DP 树形DP 记忆化搜索 贪心
基础算法 —— 代码模板链接 常用代码模板1——基础算法 排序 二分 高精度 前缀和与差分 双指针算法 位运算 离散化 区间合并 数据结构 —— 代码模板链接 常用代码模板2——数据...状态压缩DP 树形DP 记忆化搜索 贪心
北大POJ3411-Paid Roads【class】 解题报告+AC代码
连通性状态压缩dp,插头dp。acm、oi必备= =。
帮助像我一样的oi菜鸟更好更快的理解标程,在oi界能够大显身手
代码生成器!资源不错!
这个对于我们学习状态压缩的DP很有用,我一直就靠它的