vvalive 6323 상태 압축 DP
11126 단어 live
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int dp[5000][13][40],g[5][5],d[13][13],n,l,ans;
bool vi[13],ntou[13];
struct Point{
int x,y;
}p[13];
bool OK(int a,int b)
{
int x1,y1,x2,y2,i;
x1=p[a].x,y1=p[a].y;
x2=p[b].x,y2=p[b].y;
if(x1==x2){
if(y1>y2)
swap(y1,y2);
for(i=y1+1;i<y2;i++) if(!vi[g[x1][i]]||ntou[g[x1][i]])
return false;
}
if(y1==y2){
if(x1>x2)
swap(x1,x2);
for(i=x1+1;i<x2;i++) if(!vi[g[i][y1]]||ntou[g[i][y1]])
return false;
}
if(abs(x1-x2)==2&&abs(y1-y2)==2){
int x=(x1+x2)/2;
int y=(y1+y2)/2;
if(!vi[g[x][y]]||ntou[g[x][y]])
return false;
}
return true;
}
void init()
{
int i,j,cnt=0;
for(i=1;i<=3;i++){
for(j=1;j<=4;j++){
g[i][j]=++cnt;
p[cnt].x=i,p[cnt].y=j;
}
}
for(i=1;i<=12;i++){
for(j=1;j<=12;j++){
d[i][j]=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
}
}
}
void solve()
{
int i,j,k,r;
ans=0;
int N=(1<<12)-1;
for(i=0;i<12;i++)
dp[1<<i][i+1][0]=1;
for(i=1;i<=N;i++){
memset(vi,0,sizeof(vi));
for(k=0;k<12;k++) if(((1<<k)&i)) vi[k+1]=1;
for(j=0;j<12;j++) if((((1<<j)&i))&&!ntou[j+1]){
for(k=0;k<12;k++) if(((1<<k)&i)==0&&!ntou[k+1]&&OK(j+1,k+1)){
//cout<<p[j+1].x<<" "<<p[j+1].y<<" "<<p[k+1].x<<" "<<p[k+1].y<<endl;
for(r=0;r<=40;r++){
dp[i|(1<<k)][k+1][r+d[j+1][k+1]]+=dp[i][j+1][r];
}
}
}
}
for(i=1;i<=N;i++){
for(j=1;j<=12;j++){
ans+=dp[i][j][l];
}
}
}
int main()
{
int i,j,t,x,y;
init();
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
memset(vi,0,sizeof(vi));
memset(ntou,0,sizeof(ntou));
scanf("%d%d",&l,&n);
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
ntou[g[x][y]]=1;
}
if(l>=40){
printf("BAD MEMORY
");
continue;
}
solve();
if(ans)
printf("%d
",ans);
else
printf("BAD MEMORY
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vvalive 6323 상태 압축 DP텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.