POJ 2411 插头DP
阅读原文时间:2023年07月11日阅读:1

//插头DP,算是广义路径的吧。
/*
我是这样想的,定义填数的为0,未填的为1.然后,初始自然是(0,0).我还定义了整个棋盘的状态,不知是否多此一举。
这样,把轮廓线上的格子状态记录。当(I,J)上方的格子为空,必定要填一个竖的。当左边格子为空,当前可填一个横的,也可不填。
当左边格子不为空,当前格子必为空。。。AC.
*/

#include
#include
using namespace std;
int n,m;
int code[];
const int MAXL=;
const int MAXM=;
struct HASHMAP{
int hash[MAXL],next[MAXM];
__int64 f[MAXM]; int state[MAXM],alst[MAXM];
int size;
void init(){
size=;
memset(hash,-,sizeof(hash));
}
void push(int st,__int64 ans,int als){
int h=st%MAXL;
for(int i=hash[h];i!=-;i=next[i]){
if(state[i]==st){
f[i]+=ans;
return ;
}
}
f[size]=ans;
state[size]=st;
alst[size]=als;
next[size]=hash[h];
hash[h]=size++;
}
}hm[];

void decode(int st){
for(int i=;i<=m;i++){ code[i]=(st&); st=(st>>);
}
}

int encode(){
int st=; int i;
for(i=m;i>;i--){
st=(st|code[i]);
st=(st<<);
}
st=(st|code[i]);
return st;
}

void dp(int i,int j,int cur){
for(int e=;e<hm[cur].size;e++){
decode(hm[cur].state[e]);
int als=hm[cur].alst[e];
if(code[j]==){
code[j]=; als--;
hm[cur^].push(encode(),hm[cur].f[e],als);
}
else{
if(code[j-]==){
code[j]=;
hm[cur^].push(encode(),hm[cur].f[e],als+);
code[j]=code[j-]=;
hm[cur^].push(encode(),hm[cur].f[e],als-);
}
else{
code[j]=;
hm[cur^].push(encode(),hm[cur].f[e],als+);
}
}
}
}

int main(){
int i,j;
while(scanf("%d%d",&n,&m)!=EOF){
if(!n&&!m) break;
code[]=;
int cur=;
hm[cur].init();
hm[cur].push(,,);
for(i=;i<=n;i++)
for(j=;j<=m;j++){
hm[cur^].init();
dp(i,j,cur);
cur=cur^;
}
__int64 ans=;
for(i=;i<hm[cur].size;i++){
if(hm[cur].alst[i]==){
ans+=hm[cur].f[i];
}
}
printf("%I64d\n",ans);
}
return ;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章