P1713 麦当劳叔叔的难题 题解
P1713 麦当劳叔叔的难题 题解
题意
有一个
其中
比如样例的图（最短长度为 6）：
最长（长度为 10）：
思路
最短路好求，直接 bfs（其实是懒得再写一个插头 dp）。
那最长路呢？只能用插头 dp 了。
想一下三种表示方式的区别：
- 括号表示法：适用于求一条回路。
- 01 表示法：求骨牌覆盖。
- 最小表示法：求一块连通块。
显然，这道题只能用括号表示法。
但是括号表示法只能求回路，怎么求路径呢？
这个问题本蒟蒻想了一天，终于想到了。我们可以把原图围起来，在另辟一条路出来，与原路径形成回路（右下角
bfs 出来的最短路径只要加上
这时候最长路形成的回路也一定是走了外面这条路的，毕竟起点门口就有一个障碍，不走不行啊。
最后我们 dp 最长回路就行了。
Code:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=13;//加了2层
const int mod=590037;//hash表模数
int n, m, ans=0;
bool mp[N][N];//mp[][]:1空地0障碍
//括号表示法4进制
int head[mod], nxt[mod], id[mod], toth;//hash表使用链式存储
int dp[2][mod], state[2][mod], tot[2];//空间不够滚起来
int from=1, to=0;//滚动dp
int base[N];为了方便提取插头（用2进制存4进制）
bool vis[N][N];//bfs用
int dis[N][N];//bfs用存最短路
int dx[]={0, -1, 0, 1};//方向数组
int dy[]={-1, 0, 1, 0};
queue<pair<int, int> > q;
void bfs(int x, int y){//bfs求最短路
vis[x][y]=1;dis[1][1]=1;
q.push(make_pair(x, y));
while(q.size()){
pair<int, int> now=q.front();q.pop();
int xx=now.first, yy=now.second;
for(int i=0;i<4;i++){
int xxx=xx+dx[i], yyy=yy+dy[i];
if(mp[xxx][yyy] && !vis[xxx][yyy]){
dis[xxx][yyy]=dis[xx][yy]+1;
vis[xxx][yyy]=1;
q.push(make_pair(xxx, yyy));
}
}
}
}
void add(int sta, int val){//放进hash表
int key=sta%mod;
for(int i=head[key];i;i=nxt[i]){
if(state[to][id[i]]==sta){//找到是不是已经有了这个状态
dp[to][id[i]]=max(dp[to][id[i]], val);
return;
}
}
tot[to]++;//没有这个状态，新加入一个
state[to][tot[to]]=sta;
dp[to][tot[to]]=val;
toth++;
nxt[toth]=head[key];
head[key]=toth;
id[toth]=tot[to];
}
int main(){
cin>>n>>m;
n+=2;
while(m--){
int x, y;
cin>>x>>y;
mp[n-x+1][y]=1;//我是从(1,1)dp到(n,n)，所以倒过来
}
for(int j=2;j<n;j++)//放障碍围住原图
mp[2][j]=1;
for(int i=2;i<n;i++)//放障碍围住原图
mp[i][n-1]=1;
for(int j=2;j<=n;j++)//bfs不让走外面
vis[1][j]=1;
for(int i=2;i<n;i++)//bfs不让走外面
vis[i][n]=1;
for(int i=1;i<=n;i++)//取反（这样边界也就围起来了）
for(int j=1;j<=n;j++)
mp[i][j]^=1;
for(int i=1;i<=n;i++)//预处理base
base[i]=(i<<1);
tot[to]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<(n+1));j++)//行之间转移，扔掉最右边的一个没用的线
state[to][j]<<=2;
for(int j=1;j<=n;j++){
swap(from, to);
toth=tot[to]=0;
memset(head, 0, sizeof(head));//滚动数组
for(int k=1;k<=tot[from];k++){
int nowsta=state[from][k], nowans=dp[from][k];
int down=(nowsta>>base[j])&3, right=(nowsta>>base[j-1])&3;
if(!mp[i][j]){//#1：有障碍
if(!down && !right)
add(nowsta, nowans);
}else if(!down && !right){//#2:没插头
if(i!=1 || j!=1)
add(nowsta, nowans);
if(mp[i+1][j] && mp[i][j+1])
add(nowsta+(1<<base[j-1])+(2<<base[j]), nowans+1);
}else if(!down && right){//#3:只有左边插头
if(mp[i+1][j])
add(nowsta, nowans+1);//down
if(mp[i][j+1])
add(nowsta-(right<<base[j-1])+(right<<base[j]), nowans+1);//right
}else if(down && !right){//#4:只有右边插头
if(mp[i][j+1])
add(nowsta, nowans+1);//right
if(mp[i+1][j])
add(nowsta-(down<<base[j])+(down<<base[j-1]), nowans+1);//down
}else if(down==1 && right==1){//合并两个插头
int cnt=1;
for(int t=j+1;t<=n;t++){
if(((nowsta>>base[t])&3)==1)
cnt++;
if(((nowsta>>base[t])&3)==2)
cnt--;
if(cnt==0){
add(nowsta-(1<<base[t])-(1<<base[j-1])-(1<<base[j]), nowans+1);
break;
}
}
}else if(down==2 && right==2){//合并
int cnt=1;
for(int t=j-2;t>=0;t--){
if(((nowsta>>base[t])&3)==2)
cnt++;
if(((nowsta>>base[t])&3)==1)
cnt--;
if(cnt==0){
add(nowsta+(1<<base[t])-(2<<base[j-1])-(2<<base[j]), nowans+1);
break;
}
}
}else if(down==1 && right==2){//合并
add(nowsta-(right<<base[j-1])-(down<<base[j]), nowans+1);
}else if(down==2 && right==1){//形成回路
if(i==n && j==n && (nowsta-(down<<base[j])-(right<<base[j-1]))==0)
ans=max(ans, nowans+1);
}
}
}
}
bfs(1, 1);
cout<<ans-(dis[n][n]-1+2*(n-1))<<endl;//作差，输出
return 0;
}