POj 3601 하노이 한 노 타 워 (욕심)

제목: 한 노 타 문제, 하지만 그 중 하 나 는 접시 가 똑 같은 것 을 가 질 수 있다 는 것 이다.
i 종 접 시 를 이동 할 때 & & num [i] > = 2 는 역순 을 얻 었 으 나 제목 은 순 서 를 바 꿀 수 없 기 때문에 반드시 처리 해 야 한 다 는 것 을 알 수 있다.
1. 우선 순서대로 dp1 [i] = dp1 [i - 1] * 2 + num [i] ,num [i] 같은 접시 의 개수 입 니 다.
공식 적 으로 말하자면 A 에서 C 축 까지 B 축, i 종 접 시 를 빌려 i - 1 종 을 B 로 옮 기 려 면 dp1 [i - 1] 이 필요 하 다. 그리고 i 종 을 C 로 옮 기 려 면 num [i] 가 필요 하 다. 그리고 i - 1 종 을 B 에서 C 로 옮 기 려 면 dp1 [i - 1] 이 필요 하기 때문에 dp1 [i] = dp1 [i - 1] * 2 + num [i] 를 얻 을 수 있다.
2. 순서대로 dp2 [i] = 2 * dp1 [i - 1] + 2 * num [i] + dp2 [i - 1] 고려
공식 획득: num [1] - 1 개 를 보조 축 으로 이동 합 니 다. 이때 이 num [1] - 1 개의 접시 의 순 서 를 뒤 바 꾼 다음 에 첫 번 째 num [1] 에서 마지막 으로 목표 축 으로 이동 한 다음 에 보조 축 의 이동 을 다시 뒤 집어 서 순 서 를 회복 합 니 다. dp2 [1] = 2 * (num [1] - 1) + 1 을 얻 습 니 다.dp2 [i] 에 대해 x [i] = = 1 이 라면 i 종 은 순 서 를 고려 할 필요 가 없 기 때문에 dp2 [i] = dp1 [i] 그렇지 않 으 면 i 종 은 2 번 이동 하여 순서 가 변 하지 않도록 해 야 합 니 다.아니면 A 에서 C 축 까지 B 축 을 빌려 i 종 접 시 는 i - 1 종 을 순 서 를 고려 하지 않 고 C 로 옮 기 려 면 dp1 [i - 1] 이 필요 하 다.= 2 * dp1 [i - 1] + 2 * num [i] + dp2 [i - 1] 마지막 답 은 dp2 [n] 입 니 다.
코드:

#include 
#include 
using namespace std;
int dp1[105];
int dp2[105];
int num[105];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
        dp1[1]=num[1];//dp1     
        for(int i=2;i<=n;i++)
        dp1[i]=(2*dp1[i-1]+num[i])%m;
        dp2[1]=2*(num[1]-1)+1;//    
        for(int i=2;i<=n;i++)
        {
            if(num[i]==1)
            dp2[i]=dp1[i]%m;
            else
            dp2[i]=(2*dp1[i-1]+2*num[i]+dp2[i-1])%m;
        }
        printf("%d
",dp2[n]);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]

Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

POj 3601 하노이 한 노 타 워 (욕심)

좋은 웹페이지 즐겨찾기