인접하지 않는 문제-상압 Dp-HDU1565,POJ3254

먼저 만든 HDU 1565 격자 수 문제는 격자 수에서 얻은 수를 서로 인접할 수 없으며 최대 얻을 수 있는 총계가 얼마냐고 물었다
쉽게 생각할 수 있다--dp[i][j]는 현재 i행 j상태에서 얻은 수를 나타낸다. 어떻게 dp가 됩니까???우선 줄마다 방안을 찾을 수 있습니다. (좌우가 서로 인접하지 않으면 됩니다.pass state [] 에 저장하십시오.)

void find_pass()
{
    for(int i = 0;i < (1 << N);i++)
    {
        if((i & (i << 1)))continue;
        pass_state[++tot] = i;
    }
}

그리고 각 줄마다 실행 가능한 상태에 대해 이 상태에 대응하는 가치와 후속적인 상태 이동을 편리하게 하고 최대치를 구하도록 요구한다.

int array_pass[25][18000];
int get_part_sum(int x,int h)
{
    int sum = 0;
    for(int i = 0;i < N;i++)
    {
        if((x & (1 << i)) > 0)
        {
            sum += cost[h][i];
        }
    }
    return sum;
}
void save_pass_state()
{
    for(int i = 1;i <= tot;i++)
    {
        array_pass[0][i] = dp[0][i] = get_part_sum(pass_state[i],0);
        for(int j = 1;j < N;j++)
        {
            array_pass[j][i] = get_part_sum(pass_state[i],j);
        }
    }
}

처음에 첫 번째 줄의 dp값을 초기화했습니다. 첫 번째 줄이 특수하기 때문에 상하가 인접한 상황을 고려할 필요가 없습니다. 그러면 우리는 두 번째 줄부터 외층의 한 줄과 순환할 수 있습니다. 안쪽은 현재 상태이고 가장 안쪽은 위 줄의 상태입니다. 위아래가 인접하지 않은 상황을 만족시키면 상태 이동을 시도할 수 있습니다.

void find_return()
{
    for(int i = 1;i < N;i++)
    {
        for(int j = 1;j <= tot;j++)
        {
            for(int k = 1;k <= tot;k++)
            {
                if((pass_state[j] & pass_state[k]) > 0)continue;
                dp[i][j] = max(dp[i][j],dp[i - 1][k] + array_pass[i][j]);
            }
        }
    }
}
void get_ret()
{
    int ret_max = -1;
    for(int i = 1;i <= tot;i++)
    {
        ret_max = max(ret_max,dp[N - 1][i]);
    }
    printf("%d
",ret_max);
}

마지막 출력은 마지막 줄의 모든 실행 가능한 상태에서 가장 큰 출력을 선택하는 것입니다.
그 다음에 Poj3254를 보면 사실 차이가 많지 않다. 단지 이것은 전체적인 방법을 구하고 싶을 뿐이다. 그리고 실행 가능한 상태에 대한 자신의 정의도 생겼다. 서로 인접하지 않는 것이 아니라 원래의 폭력에 한 번의 선별을 추가하고 입력 상태를 만족시켜야만 계속 진행할 수 있다.
여전히 먼저 실행 가능한 불인접 (좌우) 득장대를 찾아간다

void get_ret()
{
    int ret_max = -1;
    for(int i = 1;i <= tot;i++)
    {
        ret_max = max(ret_max,dp[N - 1][i]);
    }
    printf("%d
",ret_max);
}

그리고 두 가지 판단이 생겼다. 하나는 현재 실행 중인 상태가 입력된 상태의 제한에 만족하는지 판단하는 것이다. 하나는 상하가 서로 인접하지 않음을 판단하는 것이다.

bool is_pass_mp_state(int state,int line)
{
    state = pass_state[state];
    for(int i = 0;i < M;i++)
    {
        if(((mp[line] >> i) & 1) == 0 && ((state >> i) & 1) == 1)
            return false;
    }
    return true;
}
bool is_pass_state_line_by_line(int j,int k)
{
    j = pass_state[j];
    k = pass_state[k];
    for(int i = 0;i < M;i++)
    {
        if(((j >> i) & 1) == 1 && ((k >> i) & 1 ) == 1)
            return false;
    }
    return true;
}

이렇게 dp의 기초로 첫 줄의 값을 초기화하고 층층이 업데이트합니다

void init_first_state()
{
    for(int i = 1;i <= tot;i++)
    {
        if(is_pass_mp_state(i,0))
        {
            dp[0][i] = 1;
        }
    }
}

void update_layer_upon_layer()
{
    for(int i = 1;i < N;i++)
    {
        for(int j = 1;j <= tot;j++)
        {
            for(int k = 1;k <= tot;k++)
            {
                if(is_pass_state_line_by_line(j,k) && is_pass_mp_state(j,i))
                {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }
}

마지막 방법의 총수도 얻었다.

void get_sum()
{
    int sum = 0;
    for(int i = 1;i <= tot;i++)
    {
        //cout<

언급되지 않은 곳이 하나 있는데 지도 상태를 01로 바꾸어 입력해야 하기 때문에 하기 쉽다. 아래의 위치 연산을 숙련하면 된다.

for(int i = 0;i < N;i++)
        {
            for(int j = M - 1;j >= 0;j--)
            {
                scanf("%d",&num);
                if(num)mp[i] += (1 << j);
            }
        }