Java蒙德里安动态图_蒙德里安的梦想【状压DP】
描述
求把N*M的棋盘分割成若干个1*2的的长方形，有多少种方案。
例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。
如下图所示：
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含两个整数N和M。
当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。
输出格式
每个测试用例输出一个结果，每个结果占一行。
数据范围
1≤N,M≤111≤N,M≤11
输入样例：
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例：
1
0
1
2
3
5
144
51205
题源POJ 2411
#include
#include //EOF,NULL
#include //memset
#include //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
#include //fill,reverse,next_permutation,__gcd,
#include
#include
#include
#include
#include
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define sca(x) scanf("%d", &x)
#define sca2(x, y) scanf("%d%d", &x, &y)
#define sca3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define pri(x) printf("%d\n", x)
#define pb push_back
#define mp make_pair
typedef pair P;
typedef long long ll;
const ll inf = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+;
const int maxn = ;
const int N = 1e4 + ;
int t, n, m;
int cnt, ans, ed;
ll dp[][<
int path[][];
int h, w;
void dfs(int l, int now, int pre)
{
if (l > w) {
return;
}
if (l == w) {
path[cnt][] = pre;
path[cnt++][] = now;
return;
}
dfs(l + , (now << )|, (pre << )|); // 竖放，当前行为1，上一行为0
dfs(l + , (now << )|, (pre << )); // 横放 当前行和上一行都为11
dfs(l + , (now << ), (pre << )|); //不放，上一行为1，当前行为0
}
int main()
{
while (sca2(h, w) && h && w)
{
if (h < w) {
swap(h, w);
}
cnt = ;
dfs(, , );
memset(dp, , sizeof dp);
ed = ( << w) - ;
dp[][ed] = ;
for (int i = ; i < h; i++)
{
for (int j = ; j < cnt; j++)
{
dp[i + ][path[j][]] += dp[i][path[j][]];
}
}
printf("%lld\n", dp[h][ed]);
}
return ();
}
BZOJ 1087: [SCOI2005]互不侵犯King [状压DP]
1087: [SCOI2005]互不侵犯King Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3336 Solved: 1936[Submit][ ...
nefu1109 游戏争霸赛(状压dp)
题目链接:http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=1109 //我们校赛的一个题,状压dp,还在的人用1表示,被淘汰 ...
poj3311 TSP经典状压dp(Traveling Saleman Problem)
题目链接:http://poj.org/problem?id=3311 题意:一个人到一些地方送披萨,要求找到一条路径能够遍历每一个城市后返回出发点,并且路径距离最短.最后输出最短距离即可.注意:每一 ...
[NOIP2016]愤怒的小鸟 D2 T3 状压DP
[NOIP2016]愤怒的小鸟 D2 T3 Description Kiana最近沉迷于一款神奇的游戏无法自拔. 简单来说,这款游戏是在一个平面上进行的. 有一架弹弓位于(0,0)处,每次Kiana可 ...
【BZOJ2073】[POI2004]PRZ 状压DP
[BZOJ2073][POI2004]PRZ Description 一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍 ...
bzoj3380: [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一(spfa+状压DP)
数据最多14个有宝藏的地方,所以可以想到用状压dp 可以先预处理出每个i到j的路径中最小权值的最大值dis[i][j] 本来想用Floyd写,无奈太弱调不出来..后来改用spfa 然后进行dp,这基本 ...
HDU 1074 Doing Homework (状压dp)
题意:给你N(<=15)个作业,每个作业有最晚提交时间与需要做的时间,每次只能做一个作业,每个作业超出最晚提交时间一天扣一分 求出扣的最小分数,并输出做作业的顺序.如果有多个最小分数一样的话,则 ...
【BZOJ1688】[Usaco2005 Open]Disease Manangement 疾病管理 状压DP
[BZOJ1688][Usaco2005 Open]Disease Manangement 疾病管理 Description Alas! A set of D (1 <= D <= 15) ...
【BZOJ1725】[Usaco2006 Nov]Corn Fields牧场的安排 状压DP
[BZOJ1725][Usaco2006 Nov]Corn Fields牧场的安排 Description Farmer John新买了一块长方形的牧场,这块牧场被划分成M列N行(1<=M< ...
【BZOJ1087】 [SCOI2005]互不侵犯King 状压DP
经典状压DP. f[i][j][k]=sum(f[i-1][j-cnt[k]][k]); cnt[i]放置情况为i时的国王数量 前I行放置情况为k时国王数量为J #include
随机推荐
front end about mobile web techs
WEB OF DEVICES http://www.w3.org/standards/webofdevices/ MOBILE WEB http://www.w3.org/standards/webd ...
linux下关于svn提交的时候强制写注释
在svn版本库的hooks文件夹下面,复制模版pre-commit.tmpl cp pre-commit.tmpl pre-commit chmod 777 pre-commit 1 2 1 2 na ...
深入.net(.net平台)
S2A技能点: 1.学会“自己”进行大量复杂数据的管理(数据类型.集合.xml.文件) 2.学会“优化”代码编写--- 复用.可扩展.可替换(封装.继承.多态) 什么是“跨平台”---- 您的应用程序 ...
ios UILocalNotification的使用
iOS下的Notification的使用 Notification是智能手机应用编程中非常常用的一种传递信息的机制,而且可以非常好的节省资源,不用消耗资源来不停地检查信息状态(Pooling),在iO ...
zookeeper错误
ZooKeeper JMX enabled by defaultUsing config: /data4/hadoop/zookeeper-3.4.8/bin/../conf/zoo.cfgError ...
WPF:xmal 静动态资源
POJ2299: Ultra-QuickSort-合并排序解决逆序数问题
#include #include using namespace std; long long ans; void merge(int ...
JAVA_build_ant_mapper
ant里面mapper的详细用法 ant里面mapper标签是和fileset配合使用的,目的就是把fileset取出的文件名转成指定的样式.其实看懂官方文档后,感觉真心没啥好写的.但是还是写一下 ...
GIAC全球互联网架构大会——互联网技术架构未来
GIAC全球互联网架构大会是高可用架构技术社区推出的面向架构师.技术负责人及高端技术从业人员的技术架构大会.中国拥有全球最大的互联网用户及移动互联网用户,如何使用合适的架构来搭建互联网系统,是每一个互 ...
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！