LA3621(dfs)

3080 단어
제목 대의: n을 알고 있습니다. x가 최소한 몇 번의 곱셈을 거치면 x^n에 도달할 수 있습니다.
사고방식: 곱셈과 나누기를 할 수 있기 때문에 dfs를 거슬러 올라가려면num으로 현재 걸음수를 표시하고 step로 최대 몇 걸음을 표시해야 한다
코드:
#include <iostream>
using namespace std;
#include <cstring>
#include <algorithm>
#include <stdio.h>

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

int arr[MAXN],num;

int dfs(int n,int step) {
    if(num > step)
        return 0;
    if(arr[num] == n)
        return 1;
    if(arr[num] << (step - num) < n)
        return 0;
    for(int i = 0; i <= num; i++) {
        num++;
        arr[num] = arr[num - 1] + arr[i];
        if(arr[num] <= 10000 && dfs(n,step))
            return 1;
        arr[num] = arr[num - 1] - arr[i];
        if(arr[num] > 0 && dfs(n,step))
            return 1;
        num--;
    }
    return 0;
}

int main() {
    int n;
    while(scanf("%d",&n) != EOF && n) {
        int i;
        for(i = 0;;i++) {
            arr[num = 0] = 1;
            if(dfs(n,i))
                break;
        }
        printf("%d
"
,i); } return 0; }

좋은 웹페이지 즐겨찾기