洛谷P2289 [HNOI2004]邮递员(插头dp)
2024-09-03 19:31:54
太神仙了……讲不来讲不来->这里
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int cube=1e9,mod=;
int n,m;
struct node{
int bit[];
inline void clear(){memset(bit,,sizeof(bit));}
node(){clear();}
inline void set(int t){clear();while(t)bit[++bit[]]=t%cube,t/=cube;}
inline int &operator [](int x){return bit[x];}
inline void print(){
printf("%d",bit[bit[]]);
for(int i=bit[]-;i;--i) printf("%09d",bit[i]);
putchar();
}
inline node operator +(node b){
node c;
c[]=max(bit[],b[])+;
for(int i=;i<=c[];++i)
c[i]+=bit[i]+b[i],c[i+]+=c[i]/cube,c[i]%=cube;
while(!c[c[]]) --c[];
return c;
}
inline void operator +=(node b){*this=*this+b;}
inline void operator =(int x){set(x);}
}ans;
struct Ha{
node val[mod];
int key[mod],sz,Hash[mod];
inline void init(){
memset(val,,sizeof(val)),memset(key,-,sizeof(key));
sz=,memset(Hash,,sizeof(Hash));
}
inline void newhash(int id,int v){Hash[id]=++sz,key[sz]=v;}
node &operator [](const int state){
for(int i=state%mod;;i=(i+==mod)?:i+){
if(!Hash[i]) newhash(i,state);
if(key[Hash[i]]==state) return val[Hash[i]];
}
}
}f[];
inline int find(int state,int id){return (state>>((id-)<<))&;}
inline void set(int &state,int bit,int val){bit=(bit-)<<,state|=<<bit,state^=<<bit,state|=val<<bit;}
int link(int state,int pos){
int cnt=,del=(find(state,pos)==)?:-;
for(int i=pos;i&&i<=m+;i+=del){
int plug=find(state,i);
if(plug==) ++cnt;
else if(plug==) --cnt;
if(!cnt) return i;
}
return -;
}
void solve(int x,int y){
int now=((x-)*m+y)&,last=now^,tot=f[last].sz;
f[now].init();
for(int i=;i<=tot;++i){
int state=f[last].key[i];
node val=f[last].val[i];
int plug1=find(state,y),plug2=find(state,y+);
if(link(state,y)==-||link(state,y+)==-) continue;
if(!plug1&&!plug2){if(x!=n&&y!=m)set(state,y,),set(state,y+,),f[now][state]+=val;}
else if(plug1&&!plug2){
if(x!=n) f[now][state]+=val;
if(y!=m) set(state,y,),set(state,y+,plug1),f[now][state]+=val;
}
else if(!plug1&&plug2){
if(y!=m) f[now][state]+=val;
if(x!=n) set(state,y,plug2),set(state,y+,),f[now][state]+=val;
}
else if(plug1==&&plug2==)
set(state,link(state,y+),),set(state,y,),set(state,y+,),f[now][state]+=val;
else if(plug1==&&plug2==){if(x==n&&y==m)ans+=val;}
else if(plug1==&&plug2==)set(state,y,),set(state,y+,),f[now][state]+=val;
else if(plug1==&&plug2==)
set(state,link(state,y),),set(state,y,),set(state,y+,),f[now][state]+=val;
}
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d%d",&n,&m);
if(n==||m==) return puts(""),;
if(m>n) swap(n,m);
f[].init(),f[][]=;
for(int i=;i<=n;++i){
for(int j=;j<=m;++j) solve(i,j);
if(i!=n){
int now=(i*m)&,tot=f[now].sz;
for(int j=;j<=tot;++j)
f[now].key[j]<<=;
}
}
ans+=ans,ans.print();
return ;
}
最新文章
- iOS开发——创建你自己的Framework
- ps应用
- Spring RestTemplate: 比httpClient更优雅的Restful URL访问, java HttpPost with header
- NOI2009 诗人小G
- Activiti系列:如何让Activiti-Explorer使用sql server数据库
- bootstrap实战经验
- 【Tsinghua OJ】范围查询(Range)问题
- MyEclipse-File Serarch时报错:Problems encountered during text search
- CADisplayLink
- 支持阻塞操作和轮询操作的globalfifo设备驱动代码分析以及测试代码
- 安装Ubuntu 14.04后要做的5件事情
- Activity singleInstance启动模式
- DOS头 IMAGE_DOS_HEADER
- Mysql 创建联合主键
- thinkphp 注册验证
- Struts+Spring+Hibernate的Web应用执行过程
- Java高阶语法---final
- PHP基础之$_SERVER的详细参数与说明
- Python——glob模块
- leetcode309