[조이2009] 도미노 골패.
제면
제목의 뜻
직사각형 표를 제시하는데 일부 부분에 장애물이 있는데 그 중에서 1*2의 도미노 골패(채우지 않아도 된다)를 넣으면 서로 인접한 두 줄 사이에 최소한의 골패가 가로놓여 있고 서로 인접한 두 열 사이에도 최소한의 골패가 가로놓여 방안을 구한다.
방법
편의를 위해 S(i, j, p, q)로 왼쪽 상각이 (i, j)임을 표시하고 오른쪽 상각이 (p, q)인 자사각형은 먼저 dp로 dp[i][j][p][q]를 미리 처리한다. [q]는 S(i, j, p, q)가 마음대로 골패를 놓는 방안수(행렬의 횡단 여부를 고려하지 않음)를 표시한 다음에 dp[i][j][u][q]*dp[i][u+1][p][q]는 S(i, j, p]와 uq) 사이에 가로로 된 골패가 없다는 것을 발견할 수 있다.따라서 우리는 용척으로 열의 횡단을 해결할 수 있지만 행의 횡단에 대해서는 이렇게 해답을 구할 수 없다(복잡도가 더 높다). 우리는 f[i]수조로 전 i행의 서로 인접한 두 줄 사이에 적어도 하나의 골패가 횡단하는 방안수를 나타낼 수 있다. 그러면 f[x]=t[1][x]-∑i=2x\sum{i=2}^x∑i=2xf[i-1]*t[i][x] 그 중에서 t[i][j]는 i행에서 j행까지의 횡단을 고려하지 않는 방안수를 나타낸다.두 가지 가로로 된 구법을 결합하면 답을 얻을 수 있다.
코드 #include
#include
#define ll long long
#define N 20
#define MN 40000
#define M 19901013
using namespace std;
ll m,n,dp[N][N][N][N],tmp[2][MN],f[N],num[N],top,ans;
char str[N];
bool mm[N][N];
inline ll ask(ll u,ll v)
{
return (u>>v)&1;
}
inline void work(ll w,ll u,ll v)
{
ll i,j,k,l,t,t2,zt,tot=(1 << (v-u+1))-1;
bool now=0,nxt;
for(i=0; i<=tot; i++) tmp[0][i]=0;
t2=0;for(i=u;i<=v;i++) if(mm[w][i]) t2|=(1 << (i-u));
tmp[0][t2]=1;
for(i=w+1; i<=m+1; i++)
{
zt=0;
for(j=u,t=0; j<=v; j++,t++)
{
zt|=(mm[i][j] << t);
nxt=now^1;
for(k=0; k<=tot; k++) tmp[nxt][k]=0;
for(k=0; k<=tot; k++)
{
if(!tmp[now][k]) continue;
t2=k;
if(ask(t2,t)!=mm[i][j]) t2^=(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
if(ask(k,t)) continue;
if(j!=v&&!ask(k,t+1))
{
t2=k|(1 << (t+1));
if(ask(t2,t)!=mm[i][j]) t2^=(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
}
if(!mm[i][j])
{
t2=k|(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
}
}
now=nxt;
}
dp[w][u][i-1][v]=tmp[now][zt];
}
}
int main()
{
ll i,j,k,tot,p,q,t,u,d;
cin>>m>>n;
for(i=1; i<=m; i++)
{
scanf("%s",str+1);
for(j=1; j<=n; j++)
{
mm[i][j]=(str[j]!='.');
}
}
for(i=1; i<=n; i++)
{
for(j=i; j<=n; j++)
{
for(k=1; k<=m; k++)
{
work(k,i,j);
}
}
}
tot=(1 << (n-1))-1;
for(i=0; i<=tot; i++)
{
top=0;
num[++top]=0;
for(j=0; j<n-1; j++)
{
if(ask(i,j)) num[++top]=j+1;
}
num[++top]=n;
for(d=1; d<=m; d++)
{
for(u=1; u<=d; u++)
{
t=1;
for(j=2; j<=top; j++)
{
p=num[j-1]+1,q=num[j];
t=t*dp[u][p][d][q]%M;
}
if(u==1) f[d]=t;
else f[d]-=t*f[u-1]%M,f[d]%=M;
}
}
f[m]=(f[m]+M)%M;
if(top&1) ans-=f[m];
else ans+=f[m];
ans%=M;
}
cout<<(ans+M)%M;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
간단한 dp
이 문제는 나의 이전 문장과 기본적으로 똑같다.
단지 돈의 액수를 1로 바꾸었을 뿐이다.나의 사고방식은 바로 뒤에서 앞으로 dp이다.
프로그램pra[j]가 있는데 이 시간에 i가 시작하면 dp[i]와 dp[dp[pr...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
직사각형 표를 제시하는데 일부 부분에 장애물이 있는데 그 중에서 1*2의 도미노 골패(채우지 않아도 된다)를 넣으면 서로 인접한 두 줄 사이에 최소한의 골패가 가로놓여 있고 서로 인접한 두 열 사이에도 최소한의 골패가 가로놓여 방안을 구한다.
방법
편의를 위해 S(i, j, p, q)로 왼쪽 상각이 (i, j)임을 표시하고 오른쪽 상각이 (p, q)인 자사각형은 먼저 dp로 dp[i][j][p][q]를 미리 처리한다. [q]는 S(i, j, p, q)가 마음대로 골패를 놓는 방안수(행렬의 횡단 여부를 고려하지 않음)를 표시한 다음에 dp[i][j][u][q]*dp[i][u+1][p][q]는 S(i, j, p]와 uq) 사이에 가로로 된 골패가 없다는 것을 발견할 수 있다.따라서 우리는 용척으로 열의 횡단을 해결할 수 있지만 행의 횡단에 대해서는 이렇게 해답을 구할 수 없다(복잡도가 더 높다). 우리는 f[i]수조로 전 i행의 서로 인접한 두 줄 사이에 적어도 하나의 골패가 횡단하는 방안수를 나타낼 수 있다. 그러면 f[x]=t[1][x]-∑i=2x\sum{i=2}^x∑i=2xf[i-1]*t[i][x] 그 중에서 t[i][j]는 i행에서 j행까지의 횡단을 고려하지 않는 방안수를 나타낸다.두 가지 가로로 된 구법을 결합하면 답을 얻을 수 있다.
코드 #include
#include
#define ll long long
#define N 20
#define MN 40000
#define M 19901013
using namespace std;
ll m,n,dp[N][N][N][N],tmp[2][MN],f[N],num[N],top,ans;
char str[N];
bool mm[N][N];
inline ll ask(ll u,ll v)
{
return (u>>v)&1;
}
inline void work(ll w,ll u,ll v)
{
ll i,j,k,l,t,t2,zt,tot=(1 << (v-u+1))-1;
bool now=0,nxt;
for(i=0; i<=tot; i++) tmp[0][i]=0;
t2=0;for(i=u;i<=v;i++) if(mm[w][i]) t2|=(1 << (i-u));
tmp[0][t2]=1;
for(i=w+1; i<=m+1; i++)
{
zt=0;
for(j=u,t=0; j<=v; j++,t++)
{
zt|=(mm[i][j] << t);
nxt=now^1;
for(k=0; k<=tot; k++) tmp[nxt][k]=0;
for(k=0; k<=tot; k++)
{
if(!tmp[now][k]) continue;
t2=k;
if(ask(t2,t)!=mm[i][j]) t2^=(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
if(ask(k,t)) continue;
if(j!=v&&!ask(k,t+1))
{
t2=k|(1 << (t+1));
if(ask(t2,t)!=mm[i][j]) t2^=(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
}
if(!mm[i][j])
{
t2=k|(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
}
}
now=nxt;
}
dp[w][u][i-1][v]=tmp[now][zt];
}
}
int main()
{
ll i,j,k,tot,p,q,t,u,d;
cin>>m>>n;
for(i=1; i<=m; i++)
{
scanf("%s",str+1);
for(j=1; j<=n; j++)
{
mm[i][j]=(str[j]!='.');
}
}
for(i=1; i<=n; i++)
{
for(j=i; j<=n; j++)
{
for(k=1; k<=m; k++)
{
work(k,i,j);
}
}
}
tot=(1 << (n-1))-1;
for(i=0; i<=tot; i++)
{
top=0;
num[++top]=0;
for(j=0; j<n-1; j++)
{
if(ask(i,j)) num[++top]=j+1;
}
num[++top]=n;
for(d=1; d<=m; d++)
{
for(u=1; u<=d; u++)
{
t=1;
for(j=2; j<=top; j++)
{
p=num[j-1]+1,q=num[j];
t=t*dp[u][p][d][q]%M;
}
if(u==1) f[d]=t;
else f[d]-=t*f[u-1]%M,f[d]%=M;
}
}
f[m]=(f[m]+M)%M;
if(top&1) ans-=f[m];
else ans+=f[m];
ans%=M;
}
cout<<(ans+M)%M;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
간단한 dp
이 문제는 나의 이전 문장과 기본적으로 똑같다.
단지 돈의 액수를 1로 바꾸었을 뿐이다.나의 사고방식은 바로 뒤에서 앞으로 dp이다.
프로그램pra[j]가 있는데 이 시간에 i가 시작하면 dp[i]와 dp[dp[pr...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
#include
#define ll long long
#define N 20
#define MN 40000
#define M 19901013
using namespace std;
ll m,n,dp[N][N][N][N],tmp[2][MN],f[N],num[N],top,ans;
char str[N];
bool mm[N][N];
inline ll ask(ll u,ll v)
{
return (u>>v)&1;
}
inline void work(ll w,ll u,ll v)
{
ll i,j,k,l,t,t2,zt,tot=(1 << (v-u+1))-1;
bool now=0,nxt;
for(i=0; i<=tot; i++) tmp[0][i]=0;
t2=0;for(i=u;i<=v;i++) if(mm[w][i]) t2|=(1 << (i-u));
tmp[0][t2]=1;
for(i=w+1; i<=m+1; i++)
{
zt=0;
for(j=u,t=0; j<=v; j++,t++)
{
zt|=(mm[i][j] << t);
nxt=now^1;
for(k=0; k<=tot; k++) tmp[nxt][k]=0;
for(k=0; k<=tot; k++)
{
if(!tmp[now][k]) continue;
t2=k;
if(ask(t2,t)!=mm[i][j]) t2^=(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
if(ask(k,t)) continue;
if(j!=v&&!ask(k,t+1))
{
t2=k|(1 << (t+1));
if(ask(t2,t)!=mm[i][j]) t2^=(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
}
if(!mm[i][j])
{
t2=k|(1 << t);
tmp[nxt][t2]=(tmp[nxt][t2]+tmp[now][k])%M;
}
}
now=nxt;
}
dp[w][u][i-1][v]=tmp[now][zt];
}
}
int main()
{
ll i,j,k,tot,p,q,t,u,d;
cin>>m>>n;
for(i=1; i<=m; i++)
{
scanf("%s",str+1);
for(j=1; j<=n; j++)
{
mm[i][j]=(str[j]!='.');
}
}
for(i=1; i<=n; i++)
{
for(j=i; j<=n; j++)
{
for(k=1; k<=m; k++)
{
work(k,i,j);
}
}
}
tot=(1 << (n-1))-1;
for(i=0; i<=tot; i++)
{
top=0;
num[++top]=0;
for(j=0; j<n-1; j++)
{
if(ask(i,j)) num[++top]=j+1;
}
num[++top]=n;
for(d=1; d<=m; d++)
{
for(u=1; u<=d; u++)
{
t=1;
for(j=2; j<=top; j++)
{
p=num[j-1]+1,q=num[j];
t=t*dp[u][p][d][q]%M;
}
if(u==1) f[d]=t;
else f[d]-=t*f[u-1]%M,f[d]%=M;
}
}
f[m]=(f[m]+M)%M;
if(top&1) ans-=f[m];
else ans+=f[m];
ans%=M;
}
cout<<(ans+M)%M;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
간단한 dp이 문제는 나의 이전 문장과 기본적으로 똑같다. 단지 돈의 액수를 1로 바꾸었을 뿐이다.나의 사고방식은 바로 뒤에서 앞으로 dp이다. 프로그램pra[j]가 있는데 이 시간에 i가 시작하면 dp[i]와 dp[dp[pr...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.