题解 P2090 【数字对】

HsKr · 2020-02-21 22:48:56 · 题解

爆搜使人快乐，

搜爆使人绝望。

按题意BFS

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int n,ans=0x3f3f3f3f;
struct node{
    int x,y,step;
};
queue<node> q;
map<pair<int,int>,int> m;
int bfs(){
    q.push((node){1,1,0});
    m[make_pair(1,1)]=1;
    while(!q.empty()){
        node tmp=q.front();
        q.pop();
        if(tmp.x==n||tmp.y==n){
            return tmp.step;
        }
        if(tmp.step>ans) continue;//最优性剪枝 
        if(tmp.x>n || tmp.y>n) continue;//可行性剪枝 
        if(!m[make_pair(tmp.x+tmp.y,tmp.y)]){
            q.push((node){tmp.x+tmp.y,tmp.y,tmp.step+1});
            m[make_pair(tmp.x+tmp.y,tmp.y)]=1;
        }
        if(!m[make_pair(tmp.x,tmp.x+tmp.y)]){
            q.push((node){tmp.x,tmp.x+tmp.y,tmp.step+1});
            m[make_pair(tmp.x,tmp.x+tmp.y)]=1;
        }
    }
}
int main(){
    cin>>n;
    cout<<bfs()<<endl;
    return 0;
}

TLE30分。

上述代码又臭又长，还不如一个精简的DFS呢。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,ans=0x3f3f3f3f;
int dfs(int x,int y,int step){
    if(x==n||y==n){
        ans=min(ans,step);
    }
    if(x+y<=n){
        dfs(x+y,y,step+1);
        dfs(x,x+y,step+1); 
    }
    return ans;
}
int main(){
    cin>>n;
    cout<<dfs(1,1,0)<<endl;
    return 0;
}

当然还是TLE了，60分。

我前面是怎么写的BFS

可以考虑：令step(1,1,n,x)为从(1,1)\Rightarrow(n,x)步数的最小值，那么step(1,1,n,x)=step(n,x,1,1)=step(x,n,1,1)，从尾往头搜即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int n,ans=0x3f3f3f3f;
void dfs(int x,int y,int step){
    if(step>ans) return;
    if(x==1&&y==1){
        ans=min(ans,step);//记录最小步数
        return;
    }
    if(x==y) return;//(x,x)休想到(1,1) 
    dfs(x-(x>y?y:0),y-(y>x?x:0),step+1);//如果x>y就搜(x-y,y)，否则搜(x,y-x)，由玄学得知如果两个数差太大，减成(1,1)次数会比凑在一起一减减一堆要多。
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){//枚举x 
        dfs(i,n,0);
    }
    cout<<ans<<endl;
    return 0;
}