DP 입문 POJ - 3254

POJ - 3254형 DP

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
Input Line 1: Two space-separated integers: M and N Lines 2… M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile) Output Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000. Sample Input 2 3 1 1 1 0 1 0 Sample Output 9 Hint Number the squares as follows: 1 2 3 4
There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
대체적인 제목: 길고 넓이가 고정된 농장을 제시했다. 0은 소를 방목할 수 없고, 1은 소를 방목할 수 있다. 그러나 또 하나의 요구는 임의의 두 마리의 소가 서로 인접할 수 없다는 것이다. 이것은 같은 줄에 인접한 것이냐 같은 열에 인접한 것이냐의 문제와 관련이 있다.
예에서 가능한 방우 전략은 1:1 2:2 3:3 4:4 5:1 3:1 4:1 4:3 4:3 4:3 8:1 3:4 9: 모든 땅에서 방우를 하지 않는다는 것이다.
정의 상태 dp[i][j], i행 상태가 j일 때 소를 방목하는 종수.j의 경우 우리는 2진법으로 전환하여 낮은 위치에서 높은 위치로 순서대로 1을 표시한다
소 0은 소를 방목하지 않은 것을 의미하며, 일행의 모든 상황을 나타낼 수 있다.
그럼 전이 방정식 dp[i][j]=sum(dp[i-1][k])
상태 압축 dp의 관건은 비트 연산을 잘 처리하는 것이다.
이 문제는 & 이 연산자를 사용했다.
x&(x<<1)로 한 수가 서로 인접한 두 자리가 동시에 1인지 판단하고, 만약 동시에 1인다면 하나의 값을 되돌려주고, 그렇지 않으면 0으로 되돌려주면 일부 상태를 최적화시킬 수 있다.
x & y의 브리 값으로 동일한 것이 동시에 1인지 아닌지를 판단합니다.

#include
#include
#include
#include
#include
using namespace std;
const int N = 13;
const int M = 1<>x;
				if(x==0)
					map[i]+=(1<

judge2 함수의 판단을 통해 현재의 이런 방우 방식이 현재 정해진 땅에서 실행될 수 있는지 알 수 있습니다.map[i]+=(1<
1)) 이 단계의 조작을 통해 현재 실행 중인 목장을 위치에 따라 거꾸로 얻은 결과, 예를 들어 1 0 1의 목장은 이 조작이 끝난 후의
맵의 실제 값은 010의 10진수 값, 즉 2가 맵 수조의 상응하는 위치에 저장된 다음에judge2 함수의 재판단을 통해
줄이 저장한 숫자를'와'연산을 하면 0인지 아닌지를 판단할 수 있다. 0이면 이 줄에서 다음과 같은 배치를 할 수 있다. 모르면 스스로 몇 개를 찾을 수 있다.
2진'과'조작의 예로 스스로 더욱 깊은 사고를 한다.마지막으로 서로 인접한 두 줄 사이에서judge2 함수와 유사한 조작을 해야 한다.
두 줄 사이의 같은 열의 위치는 소를 방목할 수 없기 때문에 현재 줄과judge2의 판단을 한 후에 이전 줄과 진행해야 한다
두 가지 조건이 모두 만족해야만 현재 행해지고 있는 방우 전략을 세울 수 있다는 판단이다.그리고 이 조작을 할 때 상응하는 동적 기획을 하는 거예요.
과정은 dp수조로 현재 줄의 현재 상태에서 제목을 충족시킬 수 있는 방우 전략을 기록하고, 마지막으로 for순환은 마지막 줄의 각종 상태를 반복한다.
그에 대응하는 값은 마지막으로 이 목장 아래에서 가장 가능한 소 방목 전략의 수량이다.