상압DP상해(1)-상압에서 상압DP+간단예제 옥수수밭 Corn Fields-POJ3254

emmm, 먼저 상압 DP라는 것을 이해할 때 우리는 상압이라는 개념을 이해해야 한다. 사실은 이진 연산의 개념이다. 비교적 고전적인 것은 바로 내가 쓴 상압 비DP-의 제목이다. Even Parity-Uva11464-짝수 행렬: 이것은 내가 상압 비DP에 대한 한 방법이다.https://blog.csdn.net/qq_43906000/article/details/90798220물론 그 안에서 상압이라는 개념을 이해할 수 있을 것이다. 간단하게 말하면 폭력 매거, 이진 매거 일행의 상태를 파악하고 처리한다.
바로 한 문제만 얘기해 봅시다. 포건 3254 옥수수밭, 여기는 바로 출제면입니다.

Corn Fields

Time Limit: 2000MS Memory Limit: 65536K

Description

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.
제목 대의: 밭 한 뙈기를 주고 1곳에서만 옥수수를 얻을 수 있다. 그리고 옥수수의 앞뒤 좌우에 옥수수가 있을 수 없다. 몇 가지 방법이 있느냐고 묻는다.
우리가 방금 말한 방법에 따르면 먼저 폭력적으로 매거해야 한다. 단지 이 문제는 짝수 행렬과 약간 다르다. 이 문제는 우리가 각 층의 상태를 매거해야 그의 방안수(각 줄의 실행 가능한 상태는 하나의 방안이라고 할 수 있다)를 계산할 수 있다. 그래서 우리는 폭력(0부터 비교적 편리하다):

for (int i=0; i<n; i++)  //   
	for (int j=0; j<(1<<m); j++)  //       

상태 0000000에서 모두 심지 않은 상태에서 111111까지 모두 심는 상태입니다.
그리고 이 줄의 상태에 대해 우리는 그가 입력한 텍스트에 부합되는지, 그리고 이 줄이 하나를 사이에 두고 다시 놓는 제약 조건을 충족시키는지 판정해야 한다. 그러면 우리의 코드는 확장될 수 있다.

for (int i=0; i<n; i++)  //   
	for (int j=0; j<(1<<m); j++)  //       
		if (!ok(i,j)) continue;//          

//  ok    ：
int ok(int r,int s)
{
	for (int i=0; i<m; i++){//        
		if ((s&(1<<i)) && !a[r][i]) return 0;
	}
	for (int i=0; i<m; i++){//            
		if ((s&(1<<i)) && (s&(1<<(i+1)))) return 0;
	}
	return 1;
}

여기서'&': 1&1=1,1&0=0을 설명하면 s의 i위가 1인지 아닌지를 직접 판단할 수 있다.첫 줄은continue 다음에 dp[i][j]=1을 넣는다.좋습니다. 물론 판단을 추가하는 것이 필요합니다. 다음은 아래 줄의 수를 처리하는 것입니다. 아래 줄의 수는 본 줄의 수가 놓인 상태수만 있는 것이 아니라 앞줄의 상태수도 넣습니다. 이렇게 해야 전체 방안수입니다.

for (int k=0; k<(1<<m); k++) { //        
	if ((j&k)==0) dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
}

그 중에서 j는 이 줄의 상태이다. 우리는 윗줄의 상태를 일일이 열거하여 구속 조건을 충족시킬 수 있는지 확인한다.(j&k)==0은 j와 k의 0과 1이 서로 엇갈리는 것을 가리킨다. 즉, 상태가 성립되는 것을 말한다.그러면 우리는 본 줄의 이 j상태와 모든 이전 줄의 일치하는 상태 k를 dp에 넣고 다음 줄의 준비를 합니다.
그러면 마지막 줄의 각 상태의 합은 우리의 방안 총수입니다. 다음은 AC 코드입니다. (POJ는 만능 헤더 파일을 지원하지 않습니다. (* ^; ^ *)

//#include 
#include 
using namespace std;
typedef long long ll; 
const ll mod=1e8;
int a[15][15],b[15][15];
ll ans=0,dp[15][1<<15],m;
int ok(int r,int s);
int main()
{
	int n;
	scanf ("%d%d",&n,&m);
	for (int i=0; i<n; i++){
		 for (int j=0; j<m; j++){
		 	scanf ("%d",&a[i][j]);
		 }
	}
	for (int i=0; i<n; i++){//    
		for (int j=0; j<(1<<m); j++){//        
			if (!ok(i,j)) continue;
			if (i==0) {
				dp[i][j]=1;
				continue;
			}
			for (int k=0; k<(1<<m); k++){//         
				if ((j&k)==0) dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
			}
		}
	}
	for (int i=0; i<(1<<m); i++){
		ans=(ans+dp[n-1][i])%mod;
	}
	printf ("%lld
",ans);
	return 0;
}
int ok(int r,int s)
{
	for (int i=0; i<m; i++){
		if ((s&(1<<i)) && !a[r][i]) return 0;
	}
	for (int i=0; i<m; i++){
		if ((s&(1<<i)) && (s&(1<<(i+1)))) return 0;
	}
	return 1;
}

물론 더 빠른 방법은 제약조건에 부합되는 모든 수를 저장한 다음에 매거하는 것이다. 그 다음에 우리는 그의 줄마다 제약조건에 부합되는지 판단할 필요가 없다. 단지 이것은 직관적이지 않고 이해하기 어려워서 초보자에게 이렇게 쓰는 것을 권장하지 않는다...나의 블로그 상압 DP 상해(2)에 구체적으로 소개되어 있다.