2019.01.24 bzoj3125: CITY(轮廓线dp)
2024-09-27 19:57:57
传送门
题意简述:给一个n∗mn*mn∗m的网格图,有的格子不能走,有的格子只能竖着走,有的格子只能横着走,问用一条回路覆盖所有能走的格子的方案数。
思路:
就是简单的轮廓线dpdpdp加了一点限制而已,考虑几个特判。
- 只能横着走的,限制它必须有左插头,必须没有上插头
- 只能竖着走的,限制它必须有右插头,必须没有左插头
然后就差不多了。
然后博主这个废柴因为hash表写错了一个地方调了1h
代码:
#include<bits/stdc++.h>
#define ri register int
#define change f[cur].insert(stat,sum)
using namespace std;
int n,m,mp[15][15],zx=-1,zy=-1;
char s[15];
bool cur=0;
typedef long long ll;
const int mod=1e6+7;
ll ans=0;
struct Statement{
ll sum[mod];
int sta[mod],idx[mod],tot;
inline void clear(){memset(idx,-1,sizeof(idx)),tot=0;}
inline void insert(int stat,ll sums){
int pos=stat%mod;
if(!pos)++pos;
while(~idx[pos]&&sta[idx[pos]]!=stat)pos=pos==mod-1?1:pos+1;
if(~idx[pos])sum[idx[pos]]+=sums;
else sum[idx[pos]=++tot]=sums,sta[tot]=stat;
}
}f[2];
inline int getbit(int x,int p){return (x>>((p-1)<<1))&3;}
inline void update(int&x,int p,int v){x^=(getbit(x,p)^v)<<((p-1)<<1);}
inline int findr(int stat,int p){
for(ri i=p+1,cnt=1,bit;i<=m+1;++i){
bit=getbit(stat,i);
if(bit==1)++cnt;
if(bit==2)--cnt;
if(!cnt)return i;
}
}
inline int findl(int stat,int p){
for(ri i=p-1,cnt=-1,bit;i;--i){
bit=getbit(stat,i);
if(bit==1)++cnt;
if(bit==2)--cnt;
if(!cnt)return i;
}
}
inline void solve(){
f[cur=0].clear(),f[cur].insert(0,1);
for(ri i=1;i<=n;++i){
for(ri j=1;j<=m;++j){
f[cur^=1].clear();
ll sum;
for(ri stat,p,q,tt=1;tt<=f[cur^1].tot;++tt){
stat=f[cur^1].sta[tt],sum=f[cur^1].sum[tt];
p=getbit(stat,j),q=getbit(stat,j+1);
if(!mp[i][j]){if(!(p+q))change;continue;}
if(mp[i][j]==1){
if(!(p+q)){if(mp[i][j+1]%2&&mp[i+1][j]%3)update(stat,j,1),update(stat,j+1,2),change;continue;}
if(!p){
if(mp[i][j+1]%2)change;
if(mp[i+1][j]%3)update(stat,j,q),update(stat,j+1,0),change;
continue;
}
if(!q){
if(mp[i+1][j]%3)change;
if(mp[i][j+1]%2)update(stat,j,0),update(stat,j+1,p),change;
continue;
}
if(p==1&&q==2){if(i==zx&&j==zy)ans+=sum;continue;}
update(stat,j,0),update(stat,j+1,0);
if(p==2&&q==1){change;continue;}
if(p==1&&q==1){update(stat,j+1,0),update(stat,findr(stat,j+1),1),change;continue;}
if(p==2&&q==2){update(stat,j,0),update(stat,findl(stat,j),2),change;continue;}
continue;
}
if(mp[i][j]==2){
if(q&&!p&&mp[i+1][j]%3)update(stat,j+1,0),update(stat,j,q),change;
continue;
}
if(mp[i][j]==3){
if(p&&!q&&mp[i][j+1]%2)update(stat,j,0),update(stat,j+1,p),change;
continue;
}
}
}
for(ri j=1;j<=f[cur].tot;++j)f[cur].sta[j]<<=2;
}
}
int main(){
scanf("%d%d",&n,&m);
for(ri i=1;i<=n;++i){
scanf("%s",s+1);
for(ri j=1;j<=m;++j){
if(s[j]=='#')continue;
zx=i,zy=j;
if(s[j]=='.')mp[i][j]=1;
if(s[j]=='|')mp[i][j]=2;
if(s[j]=='-')mp[i][j]=3;
}
}
solve();
cout<<ans;
return 0;
}
最新文章
- Hibernate总结(一)
- C# 文件类型
- 实现iOS前台时的推送弹窗效果
- php Output Control 函数 ob_系列函数详解
- 生成n个数的全排列【递归、回溯】
- 新手浅谈C#Task异步编程
- Java 数组的三种创建方法
- DOM的定义及DOM相关
- Vijos1734 NOI2010 海拔 平面图最小割
- cuda中时间用法
- spark-sql
- 关于css3中before与after用单冒号还是双冒号的疑虑
- 计时器 Timer
- 教程:安装禅道zentao项目管理软件github上的开发版
- 工程造价数据服务云平台(造价BIM)
- js小方法,获取知道公历生日 (‘1992-01-19’),获取阴历生日日期,属相,非简单根据年份判断-----------声明:整理自网络!!
- CentOS最基本的20个常用命令
- 结对项目3-功能增强型带基本函数计算java计算器
- 【codevs2189】数字三角形+
- 2007-10的PWX OracleCdc问题解答
热门文章
- 188. Best Time to Buy and Sell Stock IV (Array; DP)
- 前端框架(kraken、Express、Node、MVC)
- eclipse项目运行文件位置
- Ajax中什么时候用同步,什么时候用异步?
- 24-算法训练 删除数组零元素-- list的使用
- java 向上转型和向下转型
- thinkphp3.2集成QRcode生成二维码
- SQL Server 2008中的CTE递归查询得到一棵树
- CBV FBV rest framework
- Hadoop集群配置(最全面总结 )(转)