예제 6.1 골패를 깔다 UVa11270

1. 제목 설명: 클릭하여 링크 열기
2. 문제 풀이 사고방식: 본 문제는 가장 기초적인 윤곽선 동태 기획 문제이다.이런 문제의 특징은 전통적인 줄 정렬을 상태로 dp를 진행할 수 없고 들쭉날쭉한 윤곽선을 상태의 일부분으로 삼아 이동할 수 밖에 없다는 것이다.다음은 이 문제를 예로 삼아 이런 방법에 대해 이야기하자.
먼저, 우리는 다단계 정책 결정의 dp문제를 되돌아보아야 한다. 이런 문제의 해법은 보통 경계 상황의 dp값을 1로 설정한 다음에 작은 단계에서 큰 단계까지 하나하나 열거한다. 지난 단계의 각 점 j와 j의 각 후계 결점 k는 d[cur][k]+=d[1-cur][j]가 있다.그 중에서 d[cur]는 현재 계산 중인 단계입니다.이 문제는 실질적으로도 다단계의 정책 결정 문제로 단지 윤곽선으로 각 단계를 묘사할 뿐이다.
시간의 복잡도를 낮추기 위해서 우리는 항상 m를 n, m의 비교적 작은 사람으로 삼는다.다음에 우리는 위에서 아래로, 왼쪽에서 오른쪽까지의 순서에 따라 바둑판을 몇 개의 단계로 나누었다. 각 단계마다 2^m의 결점이 있는데 그 중의 매 결점은 모두 m자리의 이진수로 표시하고 각 단계에서 1은 덮어쓰고 0은 덮어쓰지 않았다는 것을 나타낸다.단계의 결정은'현재 칸을 오른쪽 하단으로 하고 골패를 놓을지, 어떤 골패를 놓을지'이다. 이렇게 하면 세 가지 상황이 있다.
(1) 놓지 않으면 현재 칸의 위쪽 칸은 반드시 1이어야 한다. 그렇지 않으면 이 결정은 실행할 수 없다.
(2) 세로로 놓으면 현재 칸이 첫 줄이 될 수 없고 현재 칸의 위쪽 칸은 0이어야 한다.
(3) 가로로 놓으면 현재 칸이 첫 번째 열이 될 수 없고 현재 칸의 위쪽은 1, 왼쪽은 0이다.
이 세 가지 상황은 모두 비트 연산으로 실현할 수 있다. 그러면 본 문제는 다단계 결정의 방식에 따라 dp를 진행할 수 있고 전체 시간의 복잡도는 O(nm2^m)이다.
설명이 필요한 점은 이 문제는 기억화 검색의 형식으로 쓸 수 있다. 첫 번째로 메모 그룹을 비우면 나중에 비울 필요가 없다.
3. 코드:

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