POJ 2411 Mondriaan's Dream【状压DP】
题目来源：http://poj.org/problem?id=2411
文章图片
文章图片
★我一开始还以为是找规律的题（不过那时候我也没学 状压DP） 现在算是第二题吧
题意： 你有长宽为2 1 的矩形，问有多少种放法组成一个n*m的大矩形
思路： 【POJ 2411 Mondriaan's Dream【状压DP】】把大矩形分为1*1的小正方形来看，然后每一行都会有m个单元最多11个，我们可以用二进制来表示每一行
然后每一层都只受他上一层的影响，而第一层我们可以枚举，然后就可以慢慢推出来了
dp[ i ][ j ] 指 前 i 层的 前 i-1 层放满且第i层状态为 j 的 方法数
当第i层 状态为 100001时 表示 第一个和第六个被占过了
所以下一层就从状态 011110 开始推
详见代码
代码：
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1<<15;
const int mod=1e9+7;
typedef long long LL;
LL n,m,tmp;
LL dp[20][1<<15];
void hhh(int k,int x,int pos)
{
if(pos==m) {dp[k][x]+=tmp;
return ;
}
hhh(k,x,pos+1);
if(pos<=m-2&&!(x&1< 推荐阅读
- 模板 poj2947 Widget Factory 高斯消元
- POJ 1027 The Same Game 模拟题
- POJ 2728 Desert King(最优比率生成树)
- 图论|POJ1364 King 差分约束
- POJ 1364 King 差分约束系统
- poj2728|poj2728 Desert King
- SPOJ DISUBSTR - Distinct Substrings or SUBST1 - New Distinct Substrings 【不同子串数目】
- POJ|POJ2728 Desert King
- OJ|POJ 2686 Traveling by Stagecoach (状态压缩DP)
- poj|poj 8469 特殊密码锁