HDU4260

Problem: The End of The World Description: 한노타 문제 변형.첫 번째 문자는 첫 번째 작은 접시가 있는 기둥을 대표하는 문자열을 드리겠습니다.최소한 몇 걸음은 걸려야 모든 접시를 B기둥으로 옮길 수 있느냐고 물었다.Solution:반복.이 귀환은 나도 처음에는 잘 몰랐는데, 나중에 자세히 생각해 보니 확실히 이렇다.돌아가는 과정은 사실 일반적인 한노타 문제를 해결하는 것과 같다.모두 앞의 N개의 접시를 어떤 기둥으로 옮긴다.이럴 때 접시가 모두 기둥에 분포되어 있는 것이 아니라면 우리가 앞의 N개의 접시를 기둥으로 옮기는 것이 이렇게 순조롭게 진행되는지 의심스러울 수도 있다.사실은 아니야.거꾸로 생각해 보면 알겠지만, 우리가 먼저 가장 작은 접시를 작은 접시 위로 옮기는 것은 반드시 할 수 있는 일이다.한노타의 규칙이 그렇기 때문이다.그러면 우리는 틀림없이 차소 이상으로 제3소로 이동할 수 있을 것이다.그러면 우리가 돌아가는 과정은 따라오는 과정의 역효과가 아니겠습니까?그래서 코드를 써서 먼저 앞의 N-1개의 접시를 보조기둥으로 옮긴 다음에 N번째 접시를 B기둥으로 옮긴 다음에 마지막으로 보조기둥에 순서가 있고 긴밀한 기둥집을 B기둥으로 옮겼다.이렇게 하면 완성이다.Code(C++):

#include <stdio.h>
#include <string.h>

#define LL long long

const int M=70;

LL dp[64];

char str[M];

void get_one_step()
{
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<64;i++)
        dp[i]=2*dp[i-1]+1;
}

LL work(int order,char to)
{
    if(!order)
        return 0;

    char now=str[order-1];
    switch(now){
    case 'A':
        //  order-1 
        if(to=='A')
            return work(order-1,to);
        //  。 order-1 ， ， order-1 
        else if(to=='B')
            return work(order-1,'C')+dp[order-1]+1;
        else if(to=='C')
            return work(order-1,'B')+dp[order-1]+1;

    case 'B':
        if(to=='A')
            return work(order-1,'C')+dp[order-1]+1;
        else if(to=='B')
            return work(order-1,to);
        else if(to=='C')
            return work(order-1,'A')+dp[order-1]+1;

    case 'C':
        if(to=='A')
            return work(order-1,'B')+dp[order-1]+1;
        else if(to=='B')
            return work(order-1,'A')+dp[order-1]+1;
        else if(to=='C')
            return work(order-1,to);
    }
    return 0;
}

int main()
{
    get_one_step();
    //get_two_step();
    while(~scanf("%s",str),str[0]!='X'){
        LL ans=work(strlen(str),'B');
        printf("%lld
",ans);
    }
    return 0;
}

나중에 인터넷에 있는 다른 사람들의 문제풀이 코드를 봤어요.유일하게 다른 것은 그가 계산에서 N번째 접시를 목표 기둥으로 이동하는 것과 앞의 N-1개의 접시를 목표 기둥으로 이동하는 것을 함께 썼다는 것이다. 즉, (1LL<(order-1))로 나의 dp[order-1]+1을 대체했다.이래도 되는 거야?나중에 나는 고등학교 때 자주 풀었던 등비수열의 문제가 생각났다. 우리는 돌아가는 이 공식을 보았다.
dp[i]=2∗dp[i−1]+1
우리 양쪽에 동시에 1을 더하자.그러면 다음과 같이 됩니다.
dp[i]+1=2∗(dp[i−1]+1)
그러면 이 공식은 dp[i]+1이 첫 번째 항목은 dp[1]+1=2이고 공비는 2의 등비수열임을 나타낸다.즉, i+1개의 접시와 앞의 i개의 접시를 기둥 위로 옮기는 데 필요한 걸음수는 다음과 같다.
dp[i]+1=2i
그래서 다음 코드가 생겼어요.

#include <stdio.h>
#include <string.h>

#define LL long long

const int M=70;

LL dp[64];

char str[M];

void get_two_step()
{
    dp[0]=1;
    LL power=1;
    for(int i=1;i<64;i++,power<<=1)
        dp[i]=2*power;
}

LL work(int order,char to)
{
    if(!order)
        return 0;

    char now=str[order-1];
    switch(now){
    case 'A':
        if(to=='A')
            return work(order-1,to);
        else if(to=='B')
            return work(order-1,'C')+dp[order-1];
        else if(to=='C')
            return work(order-1,'B')+dp[order-1];

    case 'B':
        if(to=='A')
            return work(order-1,'C')+dp[order-1];
        else if(to=='B')
            return work(order-1,to);
        else if(to=='C')
            return work(order-1,'A')+dp[order-1];

    case 'C':
        if(to=='A')
            return work(order-1,'B')+dp[order-1];
        else if(to=='B')
            return work(order-1,'A')+dp[order-1];
        else if(to=='C')
            return work(order-1,to);
    }
    return 0;
}

int main()
{
    //get_one_step();
    get_two_step();
    while(~scanf("%s",str),str[0]!='X'){
        LL ans=work(strlen(str),'B');
        printf("%lld
",ans);
    }
    return 0;
}