개요
문제가 있는 링크
플레이트 5, DP
검은색이 빨간색 위에 오도록 하노이의 탑을 몇 번이나 움직여야 하는가?
입장
- 기본적인 DP, 하노이탑 문제입니다. 하노이 탑의 전형적인 문제 2 x N-1 청크, 1 x N번째 디스크 이사에 대한 질문 dp(n) = dp(n-1)×2+1관련이 있을 수 있습니다
- 이것이 작동하는 기본적인 이유는 N 번째 타일을 이동하려면 그 위의 모든 타일이 사라져야 합니다., 그런 다음 모든 N-1 조각을 이동하려면 dp(n-1) 을 사용해야 합니다. 그러나 이 문제는 N-1 청크로 해결할 수 없습니다.
- 그렇다면 이 문제를 해결하는 방법은 무엇입니까? 요점은 하나에 두 개의 하드 드라이브 당신이해야 할 일은 그것을보고 검은 색이 위에 있거나 빨간색이 위에 있도록 두 개를 함께 접는 것입니다. 검은색 끝이 있는 블록을 B라고 하고 빨간색 끝이 있는 블록을 R이라고 가정합니다.
// n = 2, answer = 11
R1R2 0 0 // 0
R2 0 B1 // 2
0 B2 B1 // 4
R1 B2 0 // 6
R1 0 R2 // 8
0 0 R1R2 // 8+dp(1)R과 B를 번갈아 가며 4번과 8번 이동합니다. 그런 다음 끝에 dp(1)을 추가하십시오. N-1 청크를 사용한다면? dp(n-1)×3+4의 경우, 위의 절차 dp(n-1)의 계수는 1이므로 훨씬 작은 수로 해결할수있다.
// n = 3, answer = 27
R1R2R3 0 0
-> R2R3 B1 0 -> R3 B1 B2 -> R3 0 R1B2 -> 0 B3 R1B2 // 8
-> 0 B1B3 B2 -> R2 B1B3 0 -> R1R2 B3 0 -> R1R2 0 R3 // 16
-> 0 0 R1R2R3 // 16+dp(2) = 27
// n = 4, answer = 59
R1R2R3R4 0 0
-> R3R4 R1B2 0 -> R4 0 R1R2B3 -> 0 B4 R1R2B3 // 6+2+6+2 = 16
-> R1R2R3 B4 0 -> R1R2R3 0 R4 // 16+(14+2) = 32
-> 0 0 R1R2R3R4 // 32+dp(3) = 59우리의 목표는 중앙에 비엔하지만 중간에 Bn을 넣으면 오른쪽 R1R2R3…Bn-1 있을 것입니다____ 다시 왼쪽으로 이동 R1R2R3…Rn-1어떤 움직임을 만들 수 있습니다 이전 단계 두 번 필요.
- 우선 마지막 판의 방향을 바꿔야 하는 이유는 마지막 판의 방향만 바꾸는 것이 N-1 청크를 옮기는 가장 좋은 방법이고, 두 번 하면 N-1 청크를 같은 방향으로 이동할 수 있습니다. 있습니다. 즉, dp(n-1)의 계수를 최소화할 수 있다.
- 그럼 왜 두배로 하는거야? 아래 점화 방정식을 참조하십시오.
// n
R1R2...Rn -> Rn 0 R1R2...Bn-1 // count(n)
0 Bn R1R2...Bn-1 -> R1R2...Rn-1 0 Rn // set(n) = 2*count(n)+4
// n+1
R1R2...Rn+1 0 0
-> RnRn+1 R1R2...Bn-1 0 -> Rn+1 R1R2..Bn-1 Bn // count(n)+2
-> Rn+1 0 R1R2...Bn // count(n+1) = 2*count(n)+2
-> 0 Bn+1 R1R2...Bn -> R1R2...Rn 0 Rn+1
// set(n+1) = 2*count(n+1)+4 = 4*count(n)+81회 이동하는 데 Count(n)번이 걸리며, n번째 디스크를 지면으로 이동하는 데는 set(n) = 2×count(n)+4번(4번 포함)이 걸립니다. n+1은 4×count(n)+8번 걸리므로 두 배가 됩니다.
소스 코드
#include <iostream>
using namespace std;
const int R = 1e9+7;
int main () {
int n;
cin >> n;
int dp(n+1), d=8;
dp(1) = 3;
for (int i=2; i<=n; i++) {
dp(i) = (dp(i-1)+d)%R;
d = (d*2)%R;
}
cout << dp(n);
}