BZOJ 1087 SCOI 2005 상호 불가침 킹상압 DP
n<=⑨
상압 DP는 각 줄의 방안을 2진법으로 1차원으로 압축하여 f[i][j][k]를 i행으로 하고 j개 국왕의 상태가 k인 방안수를 사용한 다음에 상태를 다음과 같이 옮긴다.
f[i][j][k]=Σf[i-1][j-digit[k]][l]
그중 l&k=0, l>1&k=0, l<<1&k=0, digit[k]는 k의 2진법 중 1의 개수
폭력으로 옮기면 돼요.
롱롱 꼭 켜주세요.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
bool map[512][512],usable[512];
ll f[10][100][512],ans;
int digit[512];
bool Judge(int x,int y)
{
if(x&y)
return false;
if(x<<1&y)
return false;
if(x>>1&y)
return false;
return true;
}
bool Usable(int x)
{
if(x<<1&x)
return false;
if(x>>1&x)
return false;
return true;
}
int Get_Digit(int x)
{
int re=0;
while(x)
re+=x&1,x>>=1;
return re;
}
int main()
{
int i,j,k,l;
cin>>n>>m;
for(i=0;i<1<<n;i++)
for(j=0;j<1<<n;j++)
if( Judge(i,j) )
map[i][j]=1;
for(i=0;i<1<<n;i++)
digit[i]=Get_Digit(i);
for(i=0;i<1<<n;i++)
usable[i]=Usable(i);
f[0][0][0]=1;
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
for(k=0;k<1<<n;k++)
if(usable[k]&&digit[k]<=j)
for(l=0;l<1<<n;l++)
if(usable[l]&&map[k][l]&&digit[k]+digit[l]<=j)
f[i][j][k]+=f[i-1][j-digit[k]][l];
for(i=0;i<1<<n;i++)
ans+=f[n][m][i];
cout<<ans<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.