比赛 |
20150421 |
评测结果 |
AAAAWWWWWW |
题目名称 |
走道铺砖问题 |
最终得分 |
40 |
用户昵称 |
ztx |
运行时间 |
0.031 s |
代码语言 |
C++ |
内存使用 |
0.35 MiB |
提交时间 |
2015-04-21 11:20:43 |
显示代码纯文本
/****************************************\
* Author : ztx
* Title : [cogs] 1943. 走道铺砖问题
* ALG : 状态压缩 (dp)?
* CMT :
* Time :
\****************************************/
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
unsigned typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
if (CH == '-') NEG = true , CH = getchar() ;
while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
while (ret=getchar() , ret<'!') ;
while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
ret[0]=0;while (CH=getchar() , CH<'!') ;
while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;
}
#include <cstring>
ll bits[20] = {0ULL,1ULL,2ULL,4ULL,8ULL,16ULL,32ULL,64ULL,128ULL,256ULL,512ULL,1024ULL,2048ULL,4096ULL} ;
ll cnt[2][4096]={0ULL};
/* 记录当前行到达某状态的方案总数,和到达下一行某状态的方案总数 */
int m , n ;
ll sta1 , sta2 ;
bool now,next;
void dfs(int o) {
while (sta1&bits[o]) o ++ ;
if (o > m) { cnt[next][sta2]+=cnt[now][sta1] ; return ; }
sta2 += bits[o] ;
dfs(o+1) ;
sta2 -= bits[o] ;
if (o<m && !(sta1&bits[o+1])) dfs(o+2) ;
}
int main() {
int i;
#define READ
#ifdef READ
freopen("floor.in" ,"r",stdin ) ;
freopen("floor.out","w",stdout) ;
#endif
read(n) , read(m) ;
if (n<m) { n^=m,m^=n,n^=m; }
cnt[1][0] = 1ULL ;
Rep (i,1,n) {
now=i&1,next=now^1;
rep(sta1,0,bits[m+1]) cnt[next][sta1] = 0ULL ;
rep (sta1,0,bits[m+1])
if (cnt[now][sta1])
sta2 = 0 , dfs(1) ;
}
printf("%llu\n", cnt[next][0]) ;
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
getchar() ; getchar() ;
#endif
return 0 ;
}