首页 技术 正文
技术 2022年11月23日
0 收藏 823 点赞 4,296 浏览 3369 个字

题面:

传送门

思路:

插头dp基础教程

这个L形……第一眼看上去真的是丧病啊

但是仔细想想,实际上也就是拿一堆路径铺满一个棋盘,这个路径还是有限制的

那还有什么好说的,插头dp上啊【雾】

首先。我们定义这道题中的一个插头代表着从这个格子往插头指向的方向可以伸展一个L形

但是整张图上的所有插头不可能只有一种,因此我们要分析,可以继续延伸的L形都有哪些限制呢?

我们知道,L形的一个特点就是拐了一个弯,而且只拐了一个弯,因此我们可以定义这样的两种插头:

插头1代表一个还没有拐过弯的L形的延伸,插头2则代表一个已经拐过弯的L形的延伸

这样我们解决了定义问题,接下来看如何分类讨论

第一种情况:当前状态下,当前格子上方和左方都没有插头

这时我们需要找一个L形来把这个格子填上,那么我们可能有三种决策:

  决策一:给这个格子加一个二号下插头和一个二号右插头,此时这个格子是一个新的L形的拐角

  决策二:给这个格子加一个一号下插头,此时相当于构建了一个先向下再向右的L形,从当前格子开始

  决策三:给这个格子加一个一号右插头,此时相当于构建了一个先向右再向下的L形,从当前格子开始

第二种情况:当前状态下,当前格子上方有一个一号下插头,左方没有插头

这时相当于上面有一个L形的未拐弯的一边伸过来了,有两种决策:

  决策一:L形不拐弯,继续向下延伸,当前格子只有一个一号下插头

  决策二:L形在当前格子拐弯,L形向右延伸,当前格子只有一个二号右插头

第三种情况:当前状态下,当前格子左方有一个一号右插头,上方没有插头

与第二种情况类似,故不赘述

第四种情况:当前状态下,当前格子上方有一个二号下插头,左方没有插头

这时相当于上面有一个L形的拐过弯的一边伸过来了,有两种决策:

  决策一:L形继续延伸,当前格子有一个二号下插头

  决策二:L形在当前格子终止,当前格子没有插头

决策二时注意,如果当前处在最后一个没有障碍的格子,那么需要统计入最终答案

第五种情况:当前状态下,当前格子左方有一个二号右插头,上方没有插头

与第四种情况类似,故不赘述

第六种情况:当前状态下,当前格子左方和上方都有一号插头

此时相当于两条“臂”伸了过来,在当前格子相交,应该合并成一个L形

当前格子相当于一个L形的拐弯处,没有插头

我们发现,情况一和情况六已经覆盖了四种L形的摆放方式,同时也不会有一个二号插头一个一号插头或者两个二号插头的情况出现——它们被上文的六种情况限制了

故这种分类讨论方式可以覆盖所有情况

状态可以用四进制表示(比较快),因为状态数较多,放到哈希表里面,滚动数组处理即可

Code:

 // luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define hash deep_dark_fantasy
#define ll long long
#define MOD 20110520
using namespace std;
inline int read(){
int re=,flag=;char ch=getchar();
while(ch>''||ch<''){
if(ch=='-') flag=-;
ch=getchar();
}
while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();
return re*flag;
}
int n,m,x[][],cur,pre,ex,ey;
int st[][];ll ans[][],re;
int tot[],bit[],state[],st_tot,hash=;
struct edge{
int to,next;
}a[];
void insert(int now,ll val){
int p=now%hash;
for(int i=state[p];i;i=a[i].next){
if(st[cur][a[i].to]==now){
ans[cur][a[i].to]+=val;
ans[cur][a[i].to]%=MOD;return;
}
}
tot[cur]++;
a[++st_tot].to=tot[cur];
a[st_tot].next=state[p];
state[p]=st_tot;st[cur][tot[cur]]=now;ans[cur][tot[cur]]=val%MOD;
}
void dp(){
int i,j,k,down,right,now;ll val;
cur=;tot[cur]=;ans[cur][]=;st[cur][]=;
for(i=;i<=n;i++){
for(j=;j<=tot[cur];j++) st[cur][j]<<=;
for(j=;j<=m;j++){
memset(state,,sizeof(state));st_tot=;
pre=cur;cur^=;tot[cur]=;
for(k=;k<=tot[pre];k++){
now=st[pre][k];val=ans[pre][k];
right=(now>>bit[j-])%;down=(now>>bit[j])%;
if(!x[i][j]){//障碍格子
if(!down&&!right){
insert(now,val);continue;
}
}
if(!right&&!down){//第一种情况
if(x[i+][j]&&x[i][j+])
insert(now+((<<bit[j-])<<)+((<<bit[j])<<),val);
if(x[i+][j]) insert(now+(<<bit[j-]),val);
if(x[i][j+]) insert(now+(<<bit[j]),val);
}
if(right==&&!down){//第三种情况
if(x[i][j+]) insert(now-(<<bit[j-])+(<<bit[j]),val);
if(x[i+][j]) insert(now+(<<bit[j-]),val);
}
if(down==&&!right){//第二种情况
if(x[i+][j]) insert(now-(<<bit[j])+(<<bit[j-]),val);
if(x[i][j+]) insert(now+(<<bit[j]),val);
}
if(right==&&!down){//第五种情况
if(i==ex&&j==ey) re+=val,re%=MOD;
if(x[i][j+]) insert(now-((<<bit[j-])<<)+((<<bit[j])<<),val);
insert(now-((<<bit[j-])<<),val);
}
if(down==&&!right){//第四种情况
if(i==ex&&j==ey) re+=val,re%=MOD;
if(x[i+][j]) insert(now-((<<bit[j])<<)+((<<bit[j-])<<),val);
insert(now-((<<bit[j])<<),val);
}
if(down==&&right==){//第六种情况
if(i==ex&&j==ey) re+=val,re%=MOD;
insert(now-(<<bit[j-])-(<<bit[j]),val);
}
}
}
}
}
int main(){
int i,j;char ch;
n=read();m=read();
for(i=;i<=;i++) bit[i]=i<<;
if(n>m){
for(i=;i<=n;i++){
for(j=;j<=m;j++){
ch=getchar();
while(ch!='*'&&ch!='_') ch=getchar();
x[i][j]=(ch=='_');
if(x[i][j]) ex=i,ey=j;
}
}
}
else{
swap(n,m);
for(i=m;i>;i--){
for(j=;j<=n;j++){
ch=getchar();
while(ch!='*'&&ch!='_') ch=getchar();
x[j][i]=(ch=='_');
if(x[j][i]&&((j>ex)||(j==ex&&i>ey))) ex=j,ey=i;
}
}
}
dp();
printf("%lld",re);
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/140967.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站