2019.01.23 ural1519 Formula 1(轮廓线dp)
2024-10-19 11:46:47
传送门
轮廓线dpdpdp模板题。
题意简述:给一个放有障碍的网格图,问有多少种方法能使所有非障碍格子都在同一条哈密顿回路上面。
考虑用括号序列的写法来状压这个轮廓线。
用000表示没有插头,111表示有插头,且是左括号,222表示有插头,且是右括号。
然后分类讨论一波:
- 对于当前的格子左边,上边都有插头。
- 只有左边有插头。
- 只有上边有插头。
- 左边,上边都没有插头。
其中第一种还要分类讨论一波:
- 两个插头都是左括号。
- 两个插头都是右括号
- 左边的是左括号,右边的是右括号
- 左边的是右括号,右边的是左括号
然后注意细节转移即可,注意如果像我一样用四进制实现三进制的话要手写一波hashhashhash表。
代码:
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
using namespace tr1;
typedef long long ll;
int n,m,zx=-1,zy=-1,cur;
bool mp[15][15];
char s[15];
ll ans=0;
const int mod=1e6+7;
struct Statement{
int tot,idx[mod],sta[mod];
ll num[mod];
inline void clear(){memset(idx,-1,sizeof(idx)),tot=0;}
inline void insert(int stat,ll nume){
int pos=stat%mod;
if(!pos)++pos;
while(~idx[pos]&&sta[idx[pos]]!=stat)pos=pos==mod-1?1:pos+1;
if(~idx[pos])num[idx[pos]]+=nume;
else sta[idx[pos]=++tot]=stat,num[tot]=nume;
}
}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^=((v&3)^getbit(x,p))<<((p-1)<<1);}
inline void solve(){
cur=0,f[cur].clear(),f[cur].insert(0,1);
for(ri i=1;i<=n;++i){
for(ri j=1;j<=m;++j){
cur^=1,f[cur].clear();
for(ri tt=1;tt<=f[cur^1].tot;++tt){
int stat=f[cur^1].sta[tt],p=getbit(stat,j),q=getbit(stat,j+1);
ll dpnum=f[cur^1].num[tt];
if(!mp[i][j]){if(!(p+q))f[cur].insert(stat,dpnum);continue;}
if(!(p+q)){
if(mp[i][j+1]&&mp[i+1][j])update(stat,j,1),update(stat,j+1,2),f[cur].insert(stat,dpnum);
continue;
}
if(!p){
if(mp[i][j+1])f[cur].insert(stat,dpnum);
if(mp[i+1][j])update(stat,j,q),update(stat,j+1,0),f[cur].insert(stat,dpnum);
continue;
}
if(!q){
if(mp[i+1][j])f[cur].insert(stat,dpnum);
if(mp[i][j+1])update(stat,j,0),update(stat,j+1,p),f[cur].insert(stat,dpnum);
continue;
}
if(p==1&&q==2){if(i==zx&&j==zy)ans+=dpnum;continue;}
update(stat,j,0),update(stat,j+1,0);
if(p==2&&q==1){f[cur].insert(stat,dpnum);continue;}
if(p==1){
int cnt=1;
for(ri k=j+2;k<=m+1;++k){
int bit=getbit(stat,k);
if(bit==1)++cnt;
if(bit==2)--cnt;
if(!cnt){update(stat,k,1);break;}
}
f[cur].insert(stat,dpnum);
continue;
}
int cnt=-1;
for(ri k=j-1;k;--k){
int bit=getbit(stat,k);
if(bit==1)++cnt;
if(bit==2)--cnt;
if(!cnt){update(stat,k,2);break;}
}
f[cur].insert(stat,dpnum);
}
}
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){
mp[i][j]=s[j]=='.';
if(mp[i][j])zx=i,zy=j;
}
}
if(zx==-1)return puts("-1"),0;
solve();
cout<<ans;
return 0;
}
最新文章
- JS获得URL超链接的参数值
- 使用 Daynamic 动态添加属性
- 获取List集合中最大值的方法
- 使用ODP.NET查询数据参数顺序问题及莫名ORA-01722错误提示
- shell中一维数组值得获取
- sql 如何把查询得到的结果如何放入一个新表中
- 简单的python http接口自动化脚本
- 各个版本spring的jar包以及源码下载地址
- 【转】adobe acrobat pro修改pdf文字
- python 获取当前日期 星期
- Kendo UI开发教程(14): Kendo MVVM 数据绑定(三) Click
- Jquery实现双击表单元格可编辑
- table标签中thead、tbody、tfoot的作用
- 201521123036 《Java程序设计》第13周学习总结
- 页面获取Spring Security登录用户
- Sass 笔记
- LOJ 2409「THUPC 2017」小 L 的计算题 / Sum
- 学习 spring-boot (一)
- go标准库-log包源码学习
- eoe移动开发者大会—移动开发者的极客盛宴 2013年9月14日期待您的加入!!
热门文章
- WebForm从客户端中检测到有潜在危险的Request.Form 值的处理办法
- TCP粘包、拆包
- vue 引用公共方法(例子:截取字符串固定字数,其余显示...)
- git add和git commit
- swift - 本地通知2 - 啰嗦版
- [leetcode]445. Add Two Numbers II 两数相加II
- php使用sftp上传文件
- YII2中如何自定义全局函数
- VS2013中Nuget程序包管理器控制台使用入门(二)-如何使用Nuget提供的帮助(原创)
- 转 C++函数返回值,你必须注意的问题