POJ3254 - Corn Fields(상태 압축 DP)
4882 단어 Field
제목의 대의.
N*M 크기의 토지를 정하면 토지는 비옥함과 척박함의 구분이 있다(단위당 토지는 0,1로 척박함과 비옥함을 표시한다). 비옥한 단위 토지에 옥수수를 심으라고 요구한다. 만약에 어떤 단위 토지에 옥수수를 심었다면 그것과 인접한 네 단위 토지는 옥수수를 심는 것을 허락하지 않는다. 옥수수를 심는 방안이 얼마나 있느냐고 묻는다.(하나의 시나리오는 아님)
문제풀이
매우 기초적인 상태 압축 DP는 우리는 한 줄씩 상태 이동을 할 수 있고 2진법으로 한 줄의 상태를 나타낼 수 있다. 방정식은 다음과 같다. dp[i]j]+=dp[i-1][k]는 우리가 이전 줄의 상태 k에서 현재 줄의 상태 j로 이동할 수 있음을 나타낸다. 그러면 어떤 k가 상황에 부합되는가?j&k=0만 있으면 된다. 즉, 옥수수는 같은 열에 심기에 충분하지 않다. 심은 옥수수는 서로 인접할 수 없기 때문에 우리의 j는 2진법에 서로 인접하지 않은 두 개의 1을 만족시켜야 한다. 표현식은 (j&(j>>1)이고 제목은 비옥한 땅에만 심어야 한다. 우리는 2진법으로 어떤 줄의 비옥함과 척박한 상태를 표시한다(s로 가정한다). 그러면 j는 s의 자집을 만족시켜야 한다.이걸 어떻게 판단해야 되지?사실도 매우 간단하다. (j&s)==j만 있으면 j가 s의 서브집합이라는 것을 설명한다.
코드: #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
#define MOD 100000000
int dp[MAXN][1<<MAXN],line[MAXN];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
int a;
scanf("%d",&a);
line[i]|=a<<j;
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
if((j&line[i])==j&&((j&(j>>1))==0))
for(int k=0;k<(1<<m);k++)
if((j&k)==0)
dp[i][j]+=dp[i-1][k];
int ans=0;
for(int i=0;i<(1<<m);i++)
ans+=dp[n][i];
printf("%d
",ans%MOD);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3254 - Corn Fields(상태 압축 DP)
N*M 크기의 토지를 정하면 토지는 비옥함과 척박함의 구분이 있다(단위당 토지는 0,1로 척박함과 비옥함을 표시한다).
비옥한 단위 토지에 옥수수를 심으라고 요구한다.
만약에 어떤 단위 토지에 옥수수를 심었다면 그것...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
매우 기초적인 상태 압축 DP는 우리는 한 줄씩 상태 이동을 할 수 있고 2진법으로 한 줄의 상태를 나타낼 수 있다. 방정식은 다음과 같다. dp[i]j]+=dp[i-1][k]는 우리가 이전 줄의 상태 k에서 현재 줄의 상태 j로 이동할 수 있음을 나타낸다. 그러면 어떤 k가 상황에 부합되는가?j&k=0만 있으면 된다. 즉, 옥수수는 같은 열에 심기에 충분하지 않다. 심은 옥수수는 서로 인접할 수 없기 때문에 우리의 j는 2진법에 서로 인접하지 않은 두 개의 1을 만족시켜야 한다. 표현식은 (j&(j>>1)이고 제목은 비옥한 땅에만 심어야 한다. 우리는 2진법으로 어떤 줄의 비옥함과 척박한 상태를 표시한다(s로 가정한다). 그러면 j는 s의 자집을 만족시켜야 한다.이걸 어떻게 판단해야 되지?사실도 매우 간단하다. (j&s)==j만 있으면 j가 s의 서브집합이라는 것을 설명한다.
코드: #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
#define MOD 100000000
int dp[MAXN][1<<MAXN],line[MAXN];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
int a;
scanf("%d",&a);
line[i]|=a<<j;
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
if((j&line[i])==j&&((j&(j>>1))==0))
for(int k=0;k<(1<<m);k++)
if((j&k)==0)
dp[i][j]+=dp[i-1][k];
int ans=0;
for(int i=0;i<(1<<m);i++)
ans+=dp[n][i];
printf("%d
",ans%MOD);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3254 - Corn Fields(상태 압축 DP)
N*M 크기의 토지를 정하면 토지는 비옥함과 척박함의 구분이 있다(단위당 토지는 0,1로 척박함과 비옥함을 표시한다).
비옥한 단위 토지에 옥수수를 심으라고 요구한다.
만약에 어떤 단위 토지에 옥수수를 심었다면 그것...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
#define MOD 100000000
int dp[MAXN][1<<MAXN],line[MAXN];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
int a;
scanf("%d",&a);
line[i]|=a<<j;
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
if((j&line[i])==j&&((j&(j>>1))==0))
for(int k=0;k<(1<<m);k++)
if((j&k)==0)
dp[i][j]+=dp[i-1][k];
int ans=0;
for(int i=0;i<(1<<m);i++)
ans+=dp[n][i];
printf("%d
",ans%MOD);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3254 - Corn Fields(상태 압축 DP)N*M 크기의 토지를 정하면 토지는 비옥함과 척박함의 구분이 있다(단위당 토지는 0,1로 척박함과 비옥함을 표시한다). 비옥한 단위 토지에 옥수수를 심으라고 요구한다. 만약에 어떤 단위 토지에 옥수수를 심었다면 그것...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
