POJ2411 - Mondriaan's Dream(상태 압축 DP)
4403 단어 poj
제목의 대의.
N*M 크기의 마루를 정해 놓고 1*2 크기의 벽돌로 마루를 가득 깔아 달라고 하는데 몇 가지 방안이 있냐고요?
문제풀이
처음에 도전 프로그램 설계 경연 대회에서 본 벽돌 깔기 문제에 대한 설명입니다. 하루 이틀 동안 연구를 했지만 코드가 어떻게 쓰여졌는지 잘 몰랐습니다. 지능이 급합니다. 그 위에 격자별로 옮겼는데 신마 플러그 DP라고 합니다...아버지를 괴롭히다니...그리고 과감하게 연구를 포기했어...우리는 한 줄씩 이동하는 것이 비교적 이해하기 쉽다. 방정식은 다음과 같다. dp[i][j]+=dp[i-1][k](이전 줄의 상태 k에서 현재 상태 j로 옮길 수 있다).우리는 요구에 부합되는 상태 j와 k를 들어야 한다. 만약에 i-1행의 p열이 놓여 있지 않다면 i행의 p열은 반드시 세로 블록을 놓아야 한다. 만약에 i-1행의 p열이 놓여 있다면 i행의 p열은 놓지 않아도 되고 i-1행의 p열과 p+1열이 모두 놓여 있다면 우리는 i행의 p열과 p+1열로 벽돌을 가로로 놓을 수 있다.
우리는 dfs로 실현한다. 그러면 상술한 세 가지 상황은 각각
dfs(step+1,s1<<1|1,s2<<1,line); dfs(step+1,s1<1,s2<1|1,line)를 세로로 놓기;dfs(step+2,s1<<2|3,s2<2|3,line)를 넣지 않음;가로놓다
코드: #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
typedef long long LL;
LL dp[MAXN][1<<MAXN];
int n,m;
void dfs(int step,int s1,int s2,int line)
{
if(step==m)
{
dp[line][s1]+=dp[line-1][s2];
return;
}
dfs(step+1,s1<<1|1,s2<<1,line);
dfs(step+1,s1<<1,s2<<1|1,line);
if(step+2<=m)
dfs(step+2,s1<<2|3,s2<<2|3,line);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
{
memset(dp,0,sizeof(dp));
dp[0][(1<<m)-1]=1;
for(int i=1; i<=n; i++)
dfs(0,0,0,i);
printf("%I64d
",dp[n][(1<<m)-1]);
}
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에 따라 라이센스가 부여됩니다.
처음에 도전 프로그램 설계 경연 대회에서 본 벽돌 깔기 문제에 대한 설명입니다. 하루 이틀 동안 연구를 했지만 코드가 어떻게 쓰여졌는지 잘 몰랐습니다. 지능이 급합니다. 그 위에 격자별로 옮겼는데 신마 플러그 DP라고 합니다...아버지를 괴롭히다니...그리고 과감하게 연구를 포기했어...우리는 한 줄씩 이동하는 것이 비교적 이해하기 쉽다. 방정식은 다음과 같다. dp[i][j]+=dp[i-1][k](이전 줄의 상태 k에서 현재 상태 j로 옮길 수 있다).우리는 요구에 부합되는 상태 j와 k를 들어야 한다. 만약에 i-1행의 p열이 놓여 있지 않다면 i행의 p열은 반드시 세로 블록을 놓아야 한다. 만약에 i-1행의 p열이 놓여 있다면 i행의 p열은 놓지 않아도 되고 i-1행의 p열과 p+1열이 모두 놓여 있다면 우리는 i행의 p열과 p+1열로 벽돌을 가로로 놓을 수 있다.
우리는 dfs로 실현한다. 그러면 상술한 세 가지 상황은 각각
dfs(step+1,s1<<1|1,s2<<1,line); dfs(step+1,s1<1,s2<1|1,line)를 세로로 놓기;dfs(step+2,s1<<2|3,s2<2|3,line)를 넣지 않음;가로놓다
코드: #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
typedef long long LL;
LL dp[MAXN][1<<MAXN];
int n,m;
void dfs(int step,int s1,int s2,int line)
{
if(step==m)
{
dp[line][s1]+=dp[line-1][s2];
return;
}
dfs(step+1,s1<<1|1,s2<<1,line);
dfs(step+1,s1<<1,s2<<1|1,line);
if(step+2<=m)
dfs(step+2,s1<<2|3,s2<<2|3,line);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
{
memset(dp,0,sizeof(dp));
dp[0][(1<<m)-1]=1;
for(int i=1; i<=n; i++)
dfs(0,0,0,i);
printf("%I64d
",dp[n][(1<<m)-1]);
}
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에 따라 라이센스가 부여됩니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 15
typedef long long LL;
LL dp[MAXN][1<<MAXN];
int n,m;
void dfs(int step,int s1,int s2,int line)
{
if(step==m)
{
dp[line][s1]+=dp[line-1][s2];
return;
}
dfs(step+1,s1<<1|1,s2<<1,line);
dfs(step+1,s1<<1,s2<<1|1,line);
if(step+2<=m)
dfs(step+2,s1<<2|3,s2<<2|3,line);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
{
memset(dp,0,sizeof(dp));
dp[0][(1<<m)-1]=1;
for(int i=1; i<=n; i++)
dfs(0,0,0,i);
printf("%I64d
",dp[n][(1<<m)-1]);
}
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
