云峰菌曾经提到过的黄老师过去讲课时的摆砖块 那时百度了一下题目 想了想并没有想好怎么dp 就扔了
这两天想补动态规划知识 就去FZU做专题 然后又碰到了 就认真的想并且去做了
dp思想都在代码注释里
思想是很好想的..唯一的难点大概是 c++里面没有同或这种东西 得自己写
而我又不怎么会位运算 问了蕾姐半天也没搞懂怎么用~这个取反符号
到最后怒而手写了函数
一开始想的是 init后 输入nm都可以秒出 但是在使用~的路途上 发现至少我的方法 做这个题 不能做到init后随便输入
因为 每行 都有(1<<m)-1个砖块需要去放 而我又采用的是上下都是0 我默认去放一个竖着的砖块 这样 我dp的时候 对每种m 都要设置边界 因为上一行和这一行的砖块 我枚举出来的数字的二进制都未必有m位 如果仅仅按照~来看 如果忽略符号位什么的 也是不对的 因为后面的那些0 被忽视了
所以每个数 如果枚举不到m位 我就把它当作m位 这个设置 在qf(int x,int len)里面
由于我需要输入m后再进行init 那么时间复杂度当然会比较高 limit:1000ms time:656ms 回头我再去看别人的直接算的办法
题目的错点 long long dp %I64d
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<iostream>
using namespace std;
/// 状压dp 传说中黄老师讲的摆砖块
long long int dp[15][1<<12];
/// dp[i][k] i x k 状态
int n,m;
int qf(int x , int len)
{
int w=0;
int A[15];
memset(A,0,sizeof(A));
while(x>0)
{
w++;
A[w]=x%2;
x/=2;
}
int res=0;
for(int i=1; i<=len; i++)
{
int q=1;
if(A[i]==1)
continue;
for(int l=1; l<i; l++)
{
q*=2;
}
res+=q;
}
return res;
}
int l(int a,int b,int len)
{
return ((qf(a,len)&qf(b,len)));
}
/// 放置 1 未放置 0
/// 每次放置都进行判断
/**
枚举 ： 只枚举横向放置的砖块 砖块的可行性为judge函数
1 枚举每种状态 与上一行的进行比较 如果上1下1 可以 上1下0 可以 上0下1 不可以 上0上0 全部改为1
2 对每种上0下0的状态进行改变 即 即 使其加上 ((~a)&(~b)) 得到同或后的值
3 对这种改变之后的dp数组进行改变
4 最后输出的是dp[n][(1<<m)-1] 上a 下b 的判断
(a^b)&b!=0 continue;
**/
bool judge(int x)
{
int A[15];
int w=0;
int z;
z=x;
while(z)
{
w++;
A[w]=z%2;
z/=2;
}
for(int i=1; i<=w; i++)
{
if(A[i]==1)
{
if(i+1>w||A[i+1]!=1)
return false;
i++;
}
}
return true;
}
int len;
int sz[2000];
void ok()
{
for(int i=0; i<=(1<<m)-1; i++)
{
if(judge(i))
{
len++;
sz[len]=i;
}
}
}
void init()
{
len=0;
ok();
memset(dp,0,sizeof(dp));
for(int k=0; k<=(1<<m)-1; k++)
{
if(judge(k))
{
dp[1][k]=1;
}
}
for(int i=2; i<=n; i++)
{
for(int j=1; j<=len; j++)
{
for(int k=0; k<=(1<<m)-1; k++)
{
int a=k;
int b=sz[j];
if(((a^b)&b)!=0)
continue;
b+=l(a,b,m);
dp[i][b]+=dp[i-1][k]; }
}
}
}
int main()
{
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
init();
printf("%I64d\n",dp[n][(1<<m)-1]);
}
}