当前位置: 首页 > news >正文

Mondriaans Dream题解

洛谷原题链接:P10975 Mondriaan's Dream
看数据范围容易发现是状压DP
考虑如何规定状态
设f(i,s)为第i行,填充格式为s的方案数,其中s为二进制数,1表示在这个位置填充一个长方形并使它延伸到i+1(即以i为起点的两行一列的长方形),0表示由i-1延伸而来或填充一个长方形并使它不延伸到i+1(即在第i行放置一行两列的长方形)
转移方程很简单,dp(i,s1)= dp(i-1, s2)+1,关键在于如何判断 s1和s2是否合法


合法性判断:

  1. 如果i-1的第j位为1,代表j是一个延伸到i的长方形,所以i的第j位就一定是由i-1的第j位填充的,即 s1 & s2 == 0
  2. 对于s1,被s2填充延伸部分填充之后,不能存在一段连续奇数个0的序列(无法使用两格的长方形填充),即 s1 | s2 之后判断
// x=s1 | s2;
// w=s1.size();
bool check(int x,int w) 
{bool flag=0;for(int j=0;j<w;j++){if(!((1<<j) & x)){if(!flag) flag=1;else flag=0;}else if(flag) return 0;}if(flag) return 0; return 1;
}
  1. 考虑边界的判断,即当i=n时,s1只能等于0(无法向后面延伸)

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=(1<<11);
int dp[12][N];
int n,m;bool check(int x,int w)
{bool flag=0;for(int j=0;j<w;j++){if(!((1<<j) & x)){if(!flag) flag=1;else flag=0;}else if(flag) return 0;}if(flag) return 0; return 1;
}int sovle (int h,int w)
{if(h==1){if(w%2) return 0;else return 1;}int res=0;memset(dp,0,sizeof(dp));for(int i=0;i<(1<<w);i++) if(check(i,w)) dp[1][i]=1;for(int i=2;i<=h;i++){for(int now=0;now<(1<<w);now++){for(int bs=0;bs<(1<<w);bs++){if(now & bs) continue;if(!check((now | bs),w)) continue;dp[i][now]+=dp[i-1][bs];}if(i==h) break;}}for(int i=0;i<(1<<w);i++) res+=dp[h][i];return res;
}signed main(){cin>>n>>m;while(n or m){cout<<sovle(n,m)<<endl;cin>>n>>m;}return 0;
}
http://www.hskmm.com/?act=detail&tid=23160

相关文章:

  • 网络流 最大流 Dinic 算法
  • 2025.10.2 测试
  • 数学章节总结
  • 软件工程_作业一
  • CF VP 记录
  • LabVIEW与PLC 汽车驻车制动自动调整 - 实践
  • 04. 布局管理
  • 关于安装博客园皮肤中有关于配置音乐播放器的补充(awescnb)
  • AGC VP 记录 2
  • 2025 --【J+S 二十连测】-- 第四套 总结
  • Websocket+cpolar:如何轻松实现服务远程访问? - 教程
  • 如何用C语言实现5种基本的排序算法
  • 函数-装饰器基础知识+推导式
  • VUE - 实战 2
  • QBXT2025S刷题 Day1
  • 2025多校冲刺CSP模拟赛1(螳臂复活祭)
  • mobvista三月之旅(In Peking)
  • 大学生HTML期末大作业——HTML+CSS+JavaScript购物商城(草莓) - 指南
  • P6782 [Ynoi2008] rplexq
  • AT_agc040_b [AGC040B] Two Contests
  • AT_arc084_b [ABC077D] Small Multiple 题目分析
  • 287. 寻找重复数
  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)