分析
状压dp会TLE,考虑用轮廓线dp,
设 \(dp[i][j][S]\) 表示现在处理到 \((i,j)\) 这个位置轮廓线上状态为 \(S\) 的情况
二进制位为1表示左边或者上方有骨牌跨过轮廓线,然后分类讨论转移一下即可
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int two[11]={1,2,4,8,16,32,64,128,256,512,1024};
int n,m,al; long long f[2053],dp[2053];
int main(){
while (scanf("%d%d",&n,&m)==2&&n){
if (n<m) n^=m,m^=n,n^=m;
f[0]=1,al=1<<m;
for (int i=1;i<(1<<m);++i) f[i]=0;
memcpy(dp,f,sizeof(long long)*al);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j){
memset(f,0,sizeof(long long)*al);
for (int k=0;k<al;++k)
if ((k>>j)&1) f[k^two[j]]+=dp[k];//上一行已竖放
else{
if (j<m-1&&!((k>>(j+1))&1)) f[k^two[j+1]]+=dp[k];//横放
f[k^two[j]]+=dp[k];//竖放
}
memcpy(dp,f,sizeof(long long)*al);
}
printf("%lld\n",dp[0]);
}
return 0;
}
标签:HDU,int,Mondriaan,two,long,轮廓线,1400,dp
From: https://www.cnblogs.com/Spare-No-Effort/p/17606373.html