상태 압축 요약

본문은 주로

Wiskey 대신의 블로그 결합

개념: 상태 압축은 2진법으로 모든 상태를 보존하는 것이다. 예를 들어 총 물품이 n건이 있다면 나의 전체 상태는 2^n회이고 가장 큰 상태는 2진법으로 11을 표시한다.n 개 1...11. 이런 상태 이동 방정식 dp[11001] = dp[10001] + dp[11000] + dp[01001]를 자주 얻을 수 있는데 현재 상태는 이런 상태로만 옮길 수 있다. 일반적인 dp에 비해 어떤 장점이 있습니까?바로 2진법의 비트 연산에 있다. 일반적인 dp는 하나의 for 순환으로 상태가 이동하고 2진법의 속도가 빠르고 편리하다는 것을 나타낸다. 비트 연산의 우선순위가 비교적 낮지만 n이 비교적 크면 수조가 열리지 않기 때문에 보통 n은 1-20에서 상태 압축을 선택한다.
사용 범위:
2진법의 특성에 따라 바둑판 문제를 처리할 수 있다
1. 간단한 바둑판 문제
n*n의 바둑판이 있는데 그 위에 n개의 바둑알을 놓아야 한다. 동업자와 같은 열에 두 개의 바둑알을 초과해서는 안 된다. 너에게 몇 가지 방안이 있느냐고 묻는다.
dp[i]를 정의하면 상태가 i일 때 넣을 수 있는 종류의 수를 나타낸다. i 중의 한 분은 열의 번호를 나타낸다. 한 줄에 한 개만 넣을 수 있기 때문에 상태가 이동할 때 한 번에 한 개씩 1을 추가하는 것을 보장하면 된다.
여기에 몇 개의 비트 연산 기교가 있다
i) x&-x는 x의 뒤에서 앞의 첫 번째 0이 아닌 2진법을 얻을 수 있다. (이진법의 위치 연산은 모두 부호화에 대한 것이니 주의한다)
x 원본 = 바코드 = 바코드 = 00101
- x 오리지널 = 10101 디스카운트 = 11010 디스카운트 11011
x & -x = 00001
ii)i^x는 i를 얻을 수 있다. 이 x 다음의 수를 빼면 i=10110x=00100이면 틀리거나 한 번에 10010이다.
이렇게 하면 앞의 상태를 얻은 다음에 이 상태에 대해 우리는 다시 그로 하여금 모든 상태를 진행하고 연산하게 하여 이 i=0까지 점차적으로 얻게 한다
코드:

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 1 << 20;

int dp[maxn];

int main()

{

    int n;

    while(~scanf("%d",&n)){

        memset(dp,0,sizeof(dp));

        int i,tmp = (1 << n) - 1;

        dp[0] = 1;

        for(int i = 1; i <= tmp; i++){

            int tt = i,x;

            while(tt){

                x = tt & (-tt);

                dp[i] += dp[i^x];

                tt ^= x;

            }

        }

        printf("%d
",dp[tmp]);

    }

    return 0;

}

2. 제한된 바둑판 문제(줄마다 하나씩 놓을 수 있도록 보장)

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<time.h>

const int maxn = 1 << 20;

int dp[maxn];

int map[20][20];

int a[20];

int n;

int main()

{

    while(~scanf("%d",&n)){

        for(int i = 1; i <= n ;i++){

            a[i] = 0;

            for(int j = 1; j <= n;j++){

                map[i][j] = rand()%2;

                a[i] = a[i]*2 + map[i][j];

                printf("%d",map[i][j]);

            }

            printf("
");

        }

    int i,tmp = (1<<n)-1;

    memset(dp,0,sizeof(dp));

    dp[0] = 1;

    for(int i = 1; i <= tmp ;i++){

        int tt = i,j;

        int one[20],count = 0;

        while(tt){

            one[++count] = tt&(-tt);

            tt^=one[count];

        }//         ，        ，      

        for(int j = 1; j <= count;j++){

            if((one[j]&a[count]) == 0)//   a[count]           ，          ，    tt     count     ，     a[count]    

                dp[i] = dp[i^one[j]];

        }

    }

    printf("%d
",dp[tmp]);

    }

    return 0;

}

3. n*m의 바둑판(n,m<=80)을 주고 바둑판에 k(k<=20)개의 바둑알을 놓아서 임의의 두 바둑알이 서로 다가오지 않게 해야 한다.방안의 종류를 묻다.
정의 dp[i][j][k]는 현재 i행에 있는 상태가 s[j]인 바둑알의 수가 k인 종류의 수를 나타낸다. 마지막으로 가능한 s[j]의 모든 상황을 훑어보면 답이다.
상태 이동 방정식 dp[i][j][k]+=dp[i][p][k-c[j](모든 p의 가능성) 만족하기만 하면 (s[j]&s[p])== 0

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 1 << 10;

int s[105],c[105],dp[15][105][10];

int n,m,pn;

int top;

void dfs(int t,int state,int count,int *flag)

{

    if(t == m){

        s[++top] = state;

        c[top] = count;

        return ;

    }

    flag[t+1] = 0;

    dfs(t+1,state*2,count,flag);

    if(flag[t] == 0){

        flag[t+1] = 1;

        dfs(t+1,state*2 + 1,count+1,flag);//flag            flag[t] = 0,flag[t+1] = 1

    }

}

int main()

{

    while(~scanf("%d%d%d",&n,&m,&pn)){

        int flag[20] = {0};

        top = 0;

        if(n < m){

            n^=m;

            m^=n;

            n^=m;

        }//    ，        ，m  。   。。

        dfs(0,0,0,flag);

        memset(dp,0,sizeof(dp));

        dp[0][1][0] = 1;

        for(int i = 1; i <= n ;i++){

            for(int j = 1; j <= top; j++){

                for(int p = 1; p <= top; p++){

                    for(int k = c[j]; k <= pn; k++){

                        if((s[j]&&s[p]) == 0 && k >= c[j] + c[p])

                            dp[i][j][k] += dp[i-1][p][k-c[j]];

                    }

                }

            }

        }

    int sum = 0;

    for(int i = 1; i <= top; i++){

        sum += dp[n][i][pn];

    }

    printf("%d
",sum);

}

return 0;

}

4. n*n(n≤10)의 바둑판에 k개의 국왕(인접한 8개의 칸을 공격할 수 있음)을 올려 서로 공격할 수 없는 방안의 수를 구한다.

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 1 << 10;

int s[105],c[105],dp[15][105][10];

int n,pn;

int top;

void dfs(int t,int state, int count,int *flag)

{

    if(t == n){

        s[++top] = state;

        c[top] = count;

        return ;

    }

    flag[t] = 0;

    dfs(t+1,state*2,count,flag);

    if(flag[t-1] == 0 || t == 0){

        flag[t] = 1;

        dfs(t+1,state*2+1,count+1,flag);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&pn)){

        int flag[20] ={0};

        top = 0;

        dfs(0,0,0,flag);

        //printf("%d
",top);

        memset(dp,0,sizeof(dp));

        dp[0][1][0] = 1;

        for(int i = 1; i <= n ;i++){

            for(int j = 1; j <= top ;j++){

                for(int p = 1; p <= top; p++){

                    for(int k = c[j]; k <= pn; k++){

                        if((s[p]&s[j])||(s[j]&s[p]<<1)||(s[j]&s[p]>>1))

                            continue;

                            if(k >= (c[p] + c[j]))

                            dp[i][j][k] += dp[i-1][p][k-c[j]];

                    }

                }

            }

        }

        int sum = 0;

        for(int i = 1; i <= top;i++)

          sum +=  dp[n][i][pn] ;

        printf("%d
",sum);

    }

    return 0;

}