[백준] 1852 수 묶기

수를 1X2 or 2X1 크기의 블럭으로 묶고 , 묶인 수들의 차의 합의 최대 / 최소를 찾는문제다

비트dp를 이용해서 풀 수 있다!

테이블은 d[위치][상태] 이다 -> 여기서 상태는 (위치~위치+3)까지의 상태

0부터 마지막 칸까지 가며 상태를 보고 내가 할 수 있는 행동들을 하면 된다

내 위치에서의 상태는 2가지다

1) 내가 있는 칸이 안채워진 경우

여기서 x,y를 보고 또 판단 해야 한다

n번째 줄이 아니라면 세로 가능~!

2번째 칸이 아니고 옆칸이 비었으면 가로 가능~! 

a) 가로로 놓을 수 있는 경우 (내 옆칸도 비었을 때)

b) 세로로 놓을 수 있는 경우 (위에서부터 보며 내려오므로 무조건 가능)

2) 채워진 경우

이 때는 바로 다음 블럭으로 넘어간다 (pos+1,(state>>1))

이렇게 최대 , 최소 총 2번 구하면 된다!

문제는 숫자가 크기 때문에 long long 써야한다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define MAXN 100010
const ll inf = 1e15;
int n;
ll arr[MAXN][3], d[MAXN * 3][(1 << 3)], p[MAXN * 3][(1 << 3)];
 
ll dgo(int pos, int state) {
    if (pos == n * 3) return 0;
    ll &ret = d[pos][state];
    if (ret != -1) return ret;
    ret = -inf;
    int x = pos / 3;
    int y = pos % 3;
    if (!(state & 1)) {
        if (x != n - 1) {
            ll temp = dgo(pos + 1, (state >> 1) | (1 << 2));
            temp += abs(arr[x][y] - arr[x + 1][y]);
            ret = max(ret, temp);
        }
        if (y != 2 && !(state & 2)) {
            ll temp = dgo(pos + 2, (state >> 2));
            temp += abs(arr[x][y] - arr[x][y + 1]);
            ret = max(ret, temp);
        }
    }
    else ret = dgo(pos + 1, (state >> 1));
    return ret;
}
 
ll pgo(int pos, int state) {
    if (pos == n * 3) return 0;
    ll &ret = p[pos][state];
    if (ret != -1) return ret;
    ret = inf;
    int x = pos / 3;
    int y = pos % 3;
    if (!(state & 1)) {
        if (x != n - 1) {
            ll temp = pgo(pos + 1, (state >> 1) | (1 << 2));
            temp += abs(arr[x][y] - arr[x + 1][y]);
            ret = min(ret, temp);
        }
        if (y != 2 && !(state & 2)) {
            ll temp = pgo(pos + 2, (state >> 2));
            temp += abs(arr[x][y] - arr[x][y + 1]);
            ret = min(ret, temp);
        }
    }
    else ret = pgo(pos + 1, (state >> 1));
    return ret;
}
int main() {
    memset(d, -1, sizeof(d));
    memset(p, -1, sizeof(p));
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            scanf(" %lld", &arr[i][j]);
        }
    }
    printf("%lld\n", dgo(0, 0));
    printf("%lld\n", pgo(0, 0));
}