题解 P2559 【[AHOI2002]哈利·波特与魔法石】

· · 题解

分析一下题目 其实是一个图。但，实话实说，对于我们这种蒟蒻来说，这种图还是比较难的

首先要生成这个图的各个路径，显然路径的长度已经给了，而且能不能有魔法石（能不能开开挂）也已经告诉我们了

也就是说！！！

这个图已经出来了，边，点的信息都有了

所以，直接开始暴搜

但是要记住，如果i可以到j，那么j也可以到i

#include<bits/stdc++.h>
using namespace std;
int h[8]={0,2,6,4,8,6,10,14};
int s[8];
int start,final;
int n,tx,ty,a,maxn=-1,minn=100000000;
int dis[110][110];
int vis[110][110];
void dfs(int x,int t){
    if(x==final){
        minn=min(minn,t);
        return;
    }
    for(int i=1;i<=maxn;i++){
        if(vis[x][i]!=0){
            if(dis[x][i]) dfs(i,t+h[vis[x][i]]/2);
            else dfs(i,t+h[vis[x][i]]);
        }
    }
}
int main(){
    for(int i=1;i<=7;i++)
        cin>>s[i];
    cin>>start>>final>>n;
    for(int i=1;i<=n;i++){
        cin>>tx>>ty>>a;
        vis[tx][ty]=a;
        vis[ty][tx]=a;
        dis[tx][ty]=s[a];
        dis[ty][tx]=s[a];
        maxn=max(maxn,max(tx,ty));
    }
    dfs(start,0);
    cout<<minn<<endl;
    return 0;
}

但是。。。。。。

你会发现这题会MLE+WA,只有10分，在DFS时，系统栈会爆掉

然而下面的程序没有将“如果i可以到j，那么j也可以到i”加到程序里竟然会20分！！！

不得不说，数据太水。。。

#include<bits/stdc++.h>
using namespace std;
int h[8]={0,2,6,4,8,6,10,14};
int s[8];
int start,final;
int n,tx,ty,a,maxn=-1,minn=0x3f3f3f3f3f3f;
int dis[110][110];
int vis[110][110];
void dfs(int x,int m){
    if(x==final){
        minn=min(minn,m);
        return;
    }
    for(int i=1;i<=final;i++){
        if(vis[x][i]!=0){
            if(dis[x][i]) dfs(i,m+h[vis[x][i]]/2);
            else dfs(i,m+h[vis[x][i]]);
        }   
    }
}
int main(){
    for(int i=1;i<=7;i++)
        cin>>s[i];
    cin>>start>>final>>n;
    for(int i=1;i<=n;i++){
        cin>>tx>>ty>>a;
        vis[tx][ty]=a;
        dis[tx][ty]=s[a];
        //maxn=max(maxn,max(tx,ty));
    }
    dfs(start,0);
    cout<<minn<<endl;
    return 0;
}

再仔细分析，发现，系统栈，好像受不住

所以，我们开始一些搜索剪枝

相信许多人做过迷宫这类的题目，会想到用走一遍就打一个标记，再回溯的方法。但是在这一题，显然是不大奏效的

所以另外一个剪枝方法便很明显了

记忆化

记忆化搜索:算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。

记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。

————摘自360百科

(搜索基本上都要挂上记忆化，我将记忆化理解为搜索剪枝的必由之路）

所以如何写记忆化呢？

首先，我们发现。你会“倚门回首”。

“倚门回首”：你会发现自己在搜索的途中莫名回头，由i到j之后，再从j到i，从而将一个好好的系统栈直接MLE掉

如何解决？

开一个f数组，存放到当前位置的最小距离即可

如果f[x]小于t那么直接return，把这个分支毙掉

否则将f[x]（x表示当前位置）赋值为t(距离)

所以便显而易见了

#include<bits/stdc++.h>
using namespace std;
int h[8]={0,2,6,4,8,6,10,14};
int s[8];
int start,final;
int n,tx,ty,a,maxn=-1,minn=100000000;
int dis[110][110];
int vis[110][110];
int f[110];
void dfs(int x,int t){
    if(t>f[x]) return;
    f[x]=t;
    if(x==final){
        minn=min(minn,t);
        return;
    }
    for(int i=1;i<=maxn;i++){
        if(vis[x][i]!=0){
            if(dis[x][i]) dfs(i,t+h[vis[x][i]]/2);
            else dfs(i,t+h[vis[x][i]]);
        }
    }
}
int main(){
    for(int i=1;i<=100;i++) f[i]=100000000;
    for(int i=1;i<=7;i++)
        cin>>s[i];
    cin>>start>>final>>n;
    for(int i=1;i<=n;i++){
        cin>>tx>>ty>>a;
        vis[tx][ty]=a;
        vis[ty][tx]=a;
        dis[tx][ty]=s[a];
        dis[ty][tx]=s[a];
        maxn=max(maxn,max(tx,ty));
    }
    dfs(start,0);
    cout<<minn<<endl;
    return 0;
}

（只加了四行。。。就AC了）

CSP-J RP++