EOJ 1154 / UVA 12558 이집트 점수 문제 반복 검색 심화

우리 가 분 자 를 1 이 라 고 부 르 는 점 수 는 이집트 점수 이다.
한 점 수 를 n 개의 이집트 점수 에 더 한 형식 으로 분해 하 는 방법 은 분명 다양 할 것 이다. 예 를 들 어 59 / 211 = 1 / 4 + 1 / 36 + 1 / 633 + 1 / 3798 = 1 / 6 + 1 / 9 + 1 / 633 + 1 / 3798. 그러면 우 리 는 어떤 것 을 선택 할 것 인가?
파 티 첸 이 알려 줬 어 요.
1. 분해 에 필요 한 수 는 적 을 수록 좋다
2. 1 과 동시에 마지막 점수 가 클 수록 좋다. 즉, 분모 가 작 을 수록 좋다.
3. 1, 2 가 동시에 이 점수 들 의 분모 사전 순 서 는 작 을 수록 좋다.
그럼 이제 알고리즘 을 생각해 보 겠 습 니 다.생각 하기 쉬 운 사고.
현재 점수 a / b 가 있 습 니 다.a / b 보다 작은 이집트 점 수 는 1 / k, 1 / (k + 1), 1 / (k + 2).....
우 리 는 먼저 1 / k 를 나 눈 후에 a / b - 1 / k 를 계속 나 누 었 다. 만약 우리 가 이 길이 통 하지 않 는 다 는 것 을 발견 한다 면.우 리 는 먼저 1 / (k + 1) 을 나 눈 후에 a / b - 1 / (k + 2) 을 계속 나 누 어 보 자.만약 우리 가 이 길이 통 하지 않 는 다 는 것 을 발견 한다 면 1 / (k + 3) 로 바 꾸 어 라....................................................
즉, a / b 를 나 누 는 것 이다. 우 리 는 먼저 a / b 보다 작은 이집트 점 수 를 시도 한 다음 에 두 번 째 는 a / b 보다 작은 이집트 점 수 를 순서대로 유추 하여 원래 점수 가 0 으로 나 눌 때 까지 시도 한다.
이런 사고방식 은 dfs 가 아니 겠 습 니까? 그 해답 나 무 는 바로 깊이 우선 의 규칙 에 따라 옮 겨 다 니 는 것 입 니 다.
여기까지 생각하면 우 리 는 매우 기 쁘 게 dfs 를 쓸 수 있 지만, 쓰 면 틀림없이 이상 하 다 는 것 을 발견 할 것 이다.dfs 를 쓰기 전에 트 리 의 깊이 상한 선 을 계산 해 야 합 니 다. 그렇지 않 으 면 스 택 이 터 질 수 있 습 니 다.
이 문제 에 대해 우 리 는 매번 그것 보다 작은 이집트 점 수 를 선택해 서 나눈다.우선, 우 리 는 모든 점수 가 이집트 점수 보다 작은 첫 번 째 점 수 를 찾 을 수 있다 는 것 을 알 아야 한다. 다시 말 하면 해답 트 리 의 모든 노드 에 하위 노드 가 있다 는 것 이다.해답 나무의 깊이 는 무궁무진 하 다 는 것 이다.
만약 우리 가 매우 나 쁜 상황 에 빠진다 면, 비록 무한대 까지 는 아니 지만, 매우 깊 고 깊 게 수색 할 수 있 을 것 이다.이렇게 하면 안 된다.
지금 문제 가 어디 에 있 습 니까?dfs 깊이 찾 아 보 겠 습 니 다.해답 나무의 깊이 가 뚜렷 한 상계 가 없다 는 것 이다.이 럴 때 는 새로운 검색 방법 을 도입 해 검색 을 반복 하 라 고 한다.
반복 검색 은 dfs 와 기본적으로 같 지만 검색 의 최대 깊이 를 제한 합 니 다.만약 하나의 점수 가 가장 좋 은 방안 이 세 개의 이집트 점수 로 분해 하 는 것 이 라면 사실은 dfs 입 니 다. 우 리 는 3 층 을 검색 해 야 합 니 다.
그러면 반복 적 으로 심화 되 는 사고 에 따 르 면 우리 가 먼저 검색 층 수 를 0 층 으로 제한 하고 풀 리 지 않 는 다 는 것 이다.1 층2 층3 층이 해 가 존재 한다 면 깊이 가 계속 증가 하 는 dfs 를 통 해 우 리 는 반드시 그것 을 찾 을 수 있 을 것 이다.
교체 가 깊 어 지면 어떤 좋 은 점 이 있 습 니까?
1. 깊이 가 뚜렷 하지 않 아 검색 이 느 리 고 느 린 경 우 를 피한다.
2. dfs 소모 공간 이 적은 특징 을 계승 했다.
3. 우 리 는 깊이 상한 선 을 설 정 했 기 때문에 현재 우리 의 깊이 를 알 고 있 는 상황 에서 우 리 는 이미 알 고 있 는 정 보 를 이용 하여 가 지 를 자 를 수 있다.만약 선생님 께 서 우리 에 게 3 일 동안 1000 개의 문 제 를 쓰 라 고 하신 다 면 부적 절 한 예 를 들 어 보 세 요.우 리 는 이 임 무 를 완성 할 수 있 는 여러 가지 방법 이 있다.a 방법 에 따 르 면 다음날 밤 이 되면 우 리 는 50 개 만 했다.기 존의 상계: 3 일 1000 문제 와 우리 의 현재 깊이: 다음날 밤 까지 50 문제 만 풀 었 고 필요 한 임 무 량: 6 시간 동안 950 문 제 를 풀 었 습 니 다.우 리 는 결론 을 내 릴 수 있다. 이 임 무 는 네가 이전의 속도 로 완성 할 수 없 으 니 선생님 의 임 무 를 완성 하려 면 다른 방법 을 시도 해 봐 야 한다.예 를 들 어 우 리 는 b 방법 을 시험 해 볼 수 있다. 바로 학생 들 의 숙제 를 복사 할 수 있다. 하하.
또 모 르 는 점 은 인터넷 상에 서 교체 심화 에 관 한 설명 을 볼 수 있다.코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long int LL;
const LL INF = 0x3f3f3f3f;
const LL maxn = 1005;
LL maxd;//maxd             
LL ANS[maxn], ans[maxn];

LL gcd(LL x, LL y){return y == 0 ? x : gcd(y, x % y);}

bool is_better()//                  
{
    if (ans[maxd] != ANS[maxd]) return ans[maxd] < ANS[maxd];
    bool res = true;
    for (int i = 0; i <= maxd - 1; i++){
        if (ans[i] > ANS[i]){
            res = false;
            break;
        }
    }
    return res;
}

bool dfs(LL a, LL b, LL level, LL d){
    LL gc = gcd(a, b);
    a = a / gc;
    b = b / gc;

    if (d == maxd){
        if (a == 1 && b >= level){
            ans[d] = b;
            if (is_better()) memcpy(ANS, ans, sizeof(ans));
            return true;
        }
        return false;
    }

    bool res = false;
    for (int i = level; ; i++){
        if ((maxd - d + 1) * b <= a * i) break;//                   ，                  
        //  1/i ，        ，      1/i。               ，           0.          
        // ？        ，  ！

        if (a * i >= b){// 1/i <= a/b        
            ans[d] = i;
            if (dfs(a * i - b, b * i, i + 1, d + 1)) res = true;
        }
    }

    return res;
}

int main()
{
    //freopen("1.txt", "r", stdin);
    LL a, b;
    while (~scanf("%I64d%I64d", &a, &b)){
        memset(ANS, INF, sizeof(ANS));
        for (maxd = 0; ; maxd++){//      ，        
            if (dfs(a, b, 1, 0))
                break;
        }

        for (int i = 0; i <= maxd; i++)
            printf("%I64d%c", ANS[i], i < maxd ? ' ' : '
');
    }
    return 0;
}

EOJ 1154 / UVA 12558 이집트 점수 문제 반복 검색 심화

좋은 웹페이지 즐겨찾기