UESTC 885 方老师买表

显然是一个状压DP。

将方格的摆放分成两种:

1.水平摆放:此时所占的两个格子都记为1。

2.竖直摆放:此时底下那个格子记为1,上面那个记为0。

这样的话,每行都会有一个状态表示。

定义:dp[i][s]表示考虑已经填到第i行,这一行状态为s的方法数

转移:dp[i][s] = dp[i][s]+dp[i-1][s‘]
 (s‘为上一行的状态,当第i行和第i-1行能够满足条件时,进行转移)

先预处理出所有满足条件的第一行,然后从第二行开始转移。

最后答案为dp[n][(1<<m)-1].

当n<m时交换n和m可减小1<<m,即减少状态数。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
#define ll long long
using namespace std;
#define N 2100

ll dp[13][N];
int n,m;

int FirstLine(int state)
{
int i=0;
while(i<m)
{
if(state & (1<<i)) //第i列为1,第i+1列也存在且必须为1
{
if(i < m-1)
{
if(state & (1<<(i+1))) //第i+1列为1
i += 2;
else
return 0;
}
else
return 0;
}
else
i++;
}
return 1;
}

int Can(int ka,int kb) //ka:这一行,kb:上一行
{
int i = 0;
while(i<m)
{
if(ka & (1<<i)) //这一行i列为1
{
if(kb & (1<<i)) //如果上一行i列为1,则为两个水平块
{
if(i < m-1 && (ka & (1<<(i+1))) && (kb & (1<<(i+1))))
i += 2;
else
return 0;
}
else //上一行为0,竖着放的
i++;
}
else //这一行i列为0,上一行i列必须填充
{
if(kb & (1<<i))
i++;
else
return 0;
}
}
return 1;
}

int main()
{
int i,j,sa;
int state1,state2;
while(scanf("%d%d",&n,&m)!=EOF)
{
if((n*m)%2)
{
puts("0");
continue;
}
memset(dp,0,sizeof(dp));
if(n < m)
swap(n,m);
int MAX = (1<<m)-1;
for(sa=0;sa<=MAX;sa++)
{
if(FirstLine(sa)) //此状态可以作为第一行的状态
dp[0][sa] = 1;
}
for(i=1;i<n;i++) //行递增
{
for(state1=0;state1<=MAX;state1++)
{
for(state2=0;state2<=MAX;state2++)
{
if(Can(state1,state2))
dp[i][state1] += dp[i-1][state2];
}
}
}
printf("%lld\n",dp[n-1][MAX]);
}
return 0;
}

UESTC 885 方老师买表

时间: 06-01

UESTC 885 方老师买表的相关文章

UESTC_方老师买表 CDOJ 885

老师买表 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status 由于方老师出色的专题讲座,他的名气迅速扩散到全国各地,并通过各地的讲座赚到了很多钱,鉴于现在盛行买表,于是方老师带上了一个H×W的盒子去买表,我们假设每一个表占1×2或者2×1的空间,问方老师有多少种放置表的方式,把这个盒子填满. Input 输入有多组数据 每组数据占一行,每一行有2个正整数

UESTC 899 方老师和农场 --双连通分量的构造

首先将原图中的连通分量缩点,一定可以将原图缩成一棵树的形式,然后统计这棵树的叶子节点个数,答案就是(leaf+1)/2.这里不再证明,可以画个图看一下. (简单说明一下,首先把两个最近公共祖先最远的两个叶节点之间连接一条边,这样可以把这两个点到祖先的路径上所有点收缩到一起,因为一个形成的环一定是双连通的.然后再找两个最近公共祖先最远的两个叶节点,这样一对一对找完,恰好是(leaf+1)/2次,把所有点收缩到了一起.  --Byvoid) 怎么统计呢?用并查集缩点,可以知道,缩点后留下的边全部是原

UESTC 916 方老师的分身III --拓扑排序

做法: 如果有a<b的关系,则连一条a->b的有向边,连好所有边后,找入度为0的点作为起点,将其赋为最小的价值888,然后其所有能到的端点,价值加1,加入队列,删去上一个点,然后循环往复,直到队列为空,即每个点都赋予了一个权值为止. 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #in

UESTC 901 方老师抢银行 --Tarjan求强连通分量

思路:如果出现了一个强连通分量,那么走到这个点时一定会在强连通分量里的点全部走一遍,这样才能更大.所以我们首先用Tarjan跑一遍求出所有强连通分量,然后将强连通分量缩成点(用到栈)然后就变成了一个DAG(有向无环图),然后跑一遍DFS,不断加上遍历点的权值,如果到了网吧,则更新一遍答案,因为可以出去了. 求强连通分量时,如果low[u] == dfn[u],说明形成了一个新的强连通分量,且根为u.具体求强连通分量见:http://www.cnblogs.com/whatbeg/p/377642

UESTC 914 方老师的分身I Dijkstra

题意:求有向图的往返最短路的最长长度. 分析:求第一次到所有点的距离可以用一次Dijkstra求最短路求出来.考虑回来的路,想想就知道,从每个点回来的路即为将边的方向反转再求一次最短路后的结果. 所以此题为求两次最短路. 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define Mod 100

UESTC 900 方老师炸弹 --Tarjan求割点及删点后连通分量数

Tarjan算法. 1.若u为根,且度大于1,则为割点 2.若u不为根,如果low[v]>=dfn[u],则u为割点(出现重边时可能导致等号,要判重边) 3.若low[v]>dfn[u],则边(u,v)为桥(封死在子树内),不操作. 求割点时,枚举所有与当前点u相连的点v: 1.是重边: 忽略 2.是树边: Tarjan(v),更新low[u]=min(low[u],low[v]); 子树个数cnt+1.如果low[v] >= dfn[u],说明是割点,割点数+1 3.是回边: 更新lo

UESTC 917 方老师的分身IV --求欧拉路径

判断欧拉路径是否存在及求出字典序最小的欧拉路径问题(如果存在). 将字符串的第一个字母和最后一个字母间连边,将字母看成点,最多可能有26个点(a-z),如果有欧拉路径,还要判断是否有欧拉回路,如果有,则需要找一个字典序最小的点开始生成这条链,否则以起点开始生成链,起点即为出度比入度大1的点. 欧拉路径是否存在的判定: 1.全部点在一个联通块                               ----用并查集判联通块的数量2.所有点出度入度相等                      

UESTC 915 方老师的分身II --最短路变形

即求从起点到终点至少走K条路的最短路径. 用两个变量来维护一个点的dis,u和e,u为当前点的编号,e为已经走过多少条边,w[u][e]表示到当前点,走过e条边的最短路径长度,因为是至少K条边,所以大于K条边的当做K条边来处理就好了.求最短路的三个算法都可以做,我这里用的是SPFA,比较简洁. 代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #incl

UESTC 898 方老师和缘分 --二分图匹配+强连通分量

这题原来以为是某种匹配问题,后来好像说是强连通的问题. 做法:建图,每个方老师和它想要的缘分之间连一条有向边,然后,在给出的初始匹配中反向建边,即如果第i个方老师现在找到的是缘分u,则建边u->i.这样求出所有的强连通分量,每个强连通分量中方老师和缘分的数目一定是相等的,所以每个方老师一定可以找到与他在同一个强连通分量里的缘分,因为强连通分量中每个点都是可达的,某个方老师找到了其强连通分量中的非原配点,则该原配缘分一定可以在强连通分量中找到"新欢".可以画个图看看. 由于要构造非