题解：P1713 麦当劳叔叔的难题

qbhbh · 2024-11-24 18:49:33 · 题解

一个插头dp

题面传送门：https://www.luogu.com.cn/problem/P1713

有一个 𝑛×𝑛 的矩阵，其中有 𝑚个障碍格，问从左下角到右上角的最长路与最短路的长度差。

其中 2≤𝑛≤10,0≤𝑚≤100,1≤𝑥,𝑦≤𝑛

话不多说，直接上代码

#include <bits/stdc++.h>//万能头文件
using namespace std;
const int maxn=114514;
struct point{
    int nt,stat,maxx,minx;
}a[2][2<<12];
int n,i,j,k,m,now=0,maxx=-0x7fffffff,minx=0x7fffffff,x,y;
int nxt[maxn];
int cnt[2];
bool flag[15][15];
void insert(int stat,int maxx,int minx){
    int tmp=stat%maxn;
    for(int i=nxt[tmp];i;i=a[now][i].nt)
      if(a[now][i].stat==stat){
        a[now][i].maxx=max(a[now][i].maxx,maxx);
        a[now][i].minx=min(a[now][i].minx,minx);
        return ;
      }
    a[now][++cnt[now]].stat=stat;
    a[now][cnt[now]].maxx=maxx;
    a[now][cnt[now]].minx=minx;
    a[now][cnt[now]].nt=nxt[tmp];
    nxt[tmp]=cnt[now];
}//hash
int main() {
    memset(flag,false,sizeof(flag));
    scanf("%d%d",&n,&m);
    for(i=1;i<=n+2;i++)
      for(j=1;j<=n+2;j++)
        flag[i][j]=true;
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        flag[x+2][y+2]=false;
    }
    for(i=2;i<=n+1;i++)
      flag[i][2]=flag[2][i]=false;
    insert(0,0,0);
   //插头dp
    for(i=n+2;i>=1;i--){
        for(j=1;j<=cnt[now];j++){
            a[now][j].stat<<=2;
        }
        for(j=1;j<=n+2;j++){
            int pre=now;now^=1;cnt[now]=0;
            memset(nxt,0,sizeof(nxt));
            for(k=1;k<=cnt[pre];k++){
                int tmp1=(a[pre][k].stat>>(2*j-2))%4,tmp2=(a[pre][k].stat>>(2*j))%4;
                if(flag[i][j]==false){
                    if(tmp1==0 && tmp2==0){
                        insert(a[pre][k].stat,a[pre][k].maxx,a[pre][k].minx);
                    }
                }
                else{
                    if(tmp1==0 && tmp2==0){
                        if(flag[i][j+1]==true && flag[i-1][j]==true) insert(a[pre][k].stat+(1<<(2*j-2))+(2<<(2*j)),a[pre][k].maxx+1,a[pre][k].minx+1);
                        if(i!=n+2 || j!=1)insert(a[pre][k].stat,a[pre][k].maxx,a[pre][k].minx);
                    }
                    if(tmp1>0 && tmp2==0){
                        if(flag[i][j+1]==true) insert(a[pre][k].stat-(tmp1<<(2*j-2))+(tmp1<<(2*j)),a[pre][k].maxx+1,a[pre][k].minx+1);
                        if(flag[i-1][j]==true) insert(a[pre][k].stat,a[pre][k].maxx+1,a[pre][k].minx+1);
                    }
                    if(tmp1==0 && tmp2>0){
                        if(flag[i][j+1]==true) insert(a[pre][k].stat,a[pre][k].maxx+1,a[pre][k].minx+1);
                        if(flag[i-1][j]==true) insert(a[pre][k].stat-(tmp2<<(2*j))+(tmp2<<(2*j-2)),a[pre][k].maxx+1,a[pre][k].minx+1);
                    }
                    if(tmp1==1 && tmp2==2){
                        if(i==1 && j==n+2){
                            maxx=max(maxx,a[pre][k].maxx);
                            minx=min(minx,a[pre][k].minx);
                        }
                    }
                    if(tmp1==1 && tmp2==1){
                        int count=1;
                        for(int num=j+1;num<=n+2;num++){
                            if((a[pre][k].stat>>(num*2))%4==1) count++;
                            if((a[pre][k].stat>>(num*2))%4==2) count--;
                            if(count==0){
                                insert(a[pre][k].stat-(1<<(2*j-2))-(1<<(2*j))-(1<<(2*num)),a[pre][k].maxx+1,a[pre][k].minx+1);
                                break;
                            }
                        }
                    }
                    if(tmp1==2 && tmp2==2){
                        int count=1;
                        for(int num=j-2;num>=0;num--){
                            if((a[pre][k].stat>>(num*2))%4==1) count--;
                            if((a[pre][k].stat>>(num*2))%4==2) count++;
                            if(count==0){
                                insert(a[pre][k].stat-(2<<(2*j-2))-(2<<(2*j))+(1<<(2*num)),a[pre][k].maxx+1,a[pre][k].minx+1);
                                break;
                            }
                        }
                    }
                    if(tmp1==2 && tmp2==1) insert(a[pre][k].stat-(2<<(2*j-2))-(1<<(2*j)),a[pre][k].maxx+1,a[pre][k].minx+1);
                }
              }
        }
    }
    printf("%d",maxx-minx);
    return 0;//完美收尾，撒花
}

只是本蒟蒻第一次写题解，希望管理员大大通过