poj2411(상압dp)
아이디어는 다음과 같습니다.
직사각형에는 가로놓기, 세로놓기, 놓지 않는 세 가지 방법이 있다.i행은 i-1행의 방치와만 관계가 있기 때문에 우리는 i-1행사가 가득 차도록 보장해야 하기 때문에 현재 dp[i][state]로 i행을 표시합니다
상태가state인 경우 dp[i][now]=sum{dp[i-1][pre]}.
가로놓다
만약에 i행의 d열에서 우리가 가로로 놓기를 선택한다면 i행의 d열과 d+1열은 모두 1이고 i-1행의 d열과 d+1열도 반드시 1(꽉 차게 보장)이어야 하며 상태가 다음과 같이 옮겨야 한다.
d=d+2,now=now<<2|3,pre=pre<<2|3.
세로
i행의 d열에서 우리는 세로로 놓기를 선택한다. 그러면 i행의 d열은 1이고 i-1행의 d열은 0이어야 한다. (우리는 세로로 놓았기 때문에 앞줄이 비어 있지 않으면 어떻게 내려놓을 수 있습니까) 상태 이동:
d=d+1,now=now<<1|1,pre=pre<<1.
괜찮다
i행의 d열은 무방하다. 그러면 i-1행의 d열은 틀림없이 1이다. (꽉 차게 보장), 상태 이동:
d=d+1,now=now<<1,pre=pre<<1|1.
이 문제는 진심으로 이해하지 못한다는 것을 점차적으로 나타내기 때문에 기억을 최적화하여 검색해 보자.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef __int64 lld;
#define oo 0x3f3f3f3f
#define Mod 1000000007
#define maxn (1<<11)+1
lld dp[maxn][12];
int n,m;
void dfs(int r,int c,int now,int pre)
{
if(c==m)
{
dp[now][r]+=dp[pre][r-1];
return ;
}
//
dfs(r,c+1,now<<1|1,pre<<1);
//
if(c+2<=m)
dfs(r,c+2,now<<2|3,pre<<2|3);
//
dfs(r,c+1,now<<1,pre<<1|1);
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
if(n*m&1)
{
puts("0");
continue;
}
int all=(1<<m)-1;
memset(dp,0,sizeof dp);
dp[all][0]=1;//0
for(int i=1;i<=n;i++)
dfs(i,0,0,0);
printf("%I64d
",dp[all][n]);//
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
