POJ2411 Mondriaan's Dream 아웃라인 dp
2175 단어 poj
제목은 1*2의 도미노 갈비로 크기 n*m(n, m<=11)의 바둑판을 채워서 채우는 방법이 얼마나 다른지 물어보는 것이다.실행 가능한 해법은 윤곽선 dp이다.만약에 우리가 위에서 아래로, 왼쪽에서 오른쪽으로 채운다면 우리는 우리가 현재 (i, j)칸을 채웠을 때 그 앞에 있는 (i', j')는 사실 이미 반드시 채웠기 때문에 실제로 채우지 않았을 때 윤곽선의 부분에 있고 여기에는 구체적인 것이 없다는 것을 발견할 수 있다.
1
1
1
1
1
1
x
x
x
x
위의 그림에서 보듯이 우리가 빨간색의 x칸을 채울 때 앞의 (i', j')는 반드시 1이다. 실제로 우리가 고려해야 할 것은 x의 부분이다. 이 부분은 소위 윤곽선이다. x의 수치는 확실하지 않을 수 있기 때문에 우리는 비트 압축으로 xxxx의 상태를 나타낼 수 있다.옮길 때 근거하는 것은 바로 세 가지 상황이다. 하나는 빨간색의 x가 이미 채워졌다. 이럴 때 놓지 않아도 된다. 상응하는 옮길 상황, 그리고 빨간색의 x가 채워지지 않아서 가로놓기와 세로놓기를 할 수 있다.
제자리에서 압축하기 때문에 요구되는 것은 바둑판은 반드시 좁은 테두리의 특성을 가지고 1차원적으로는 반드시 10 정도가 되어야 한다. 각 칸은 하나의 단계이기 때문에 매번 2^m의 상태를 옮기고 각 상태의 이동의 복잡도는 O(1)이기 때문에 전체적인 복잡도는 O(n*m*2^m)이다.
그리고 일부 변형은 바둑판 자체에 이미 약간의 장애가 있다는 것이다. 이것은 이동할 때 주의를 기울이면 된다. 내 뒤에도 한번 해 보겠다.
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
int n, m;
ll dp[2][1 << 12]; //
int main()
{
while (cin >> n >> m &&(n||m))
{
memset(dp, 0, sizeof(dp));
ll *cur, *next;
cur = dp[0]; next = dp[1];
cur[0] = 1;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
memset(dp[(i*m+j+1)&1], 0, sizeof(dp[(i*m+j+1)&1]));
cur = dp[(i*m + j) & 1]; next = dp[(i*m + j + 1) & 1];
for (int k = 0; k < 1 << m; k++){
// ，
if ((k >> j) & 1){
next[k & ~(1 << j)] += cur[k];
}
else{
//
if (j + 1 < m && !(k >> (j + 1) & 1)){
next[k | 1 << (j + 1)] += cur[k];
}
//
if (i + 1 < n){
next[k | 1 << j] += cur[k];
}
}
}
}
}
printf("%lld
", next[0]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
