题解 P2090 【数字对】

Itache · 2017-08-29 09:48:22 · 题解

这题可用搜索，如果直接从头搜到尾只有50分，所以借鉴了一下楼下的方法，枚举到n时另一个数的每一种情况，从后往前搜，再加上剪枝，即可AC。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int minn=2000000000;
void search(int x,int y,int r){//X：第一个数；y：二；r:次数 
    if(r>minn)
        return ;//最优性剪枝 
    //printf("%d %d %d\n",x,y,r);
    if(x==1&&y==1){
        minn=min(minn,r);
        return ;

}//更新 if(x<1||y<1)

        return ;//边界 
    if(x>y)
        search(x-y,y,r+1);
    else if(y>x)search(x,y-x,r+1);//这两步很重要，可以使一棵
    //2叉树变为一条链 
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=2;i<n;i++)//枚举每一种情况 
        search(i,n,0);
    printf("%d",minn);
    return 0;
}