[DP] 호텔 문제풀이 동태 기획 중의 상태 설계 방법에 대해 간단히 말하다.

n개의 방이 있는데 각 방에는 7명보다 적고 두 개의 인접한 방의 거리는 하나이며 각 방은 0 또는 4 또는 7명이 묵을 수 있으며 총 이동 거리가 가장 작기를 바란다.직관적 감각 DP는 dp[i][j]로 설계되었고 첫 번째는 방을 표시하고 두 번째는 인원수를 표시한 후에 도저히 할 수 없다는 것을 발견했다.(웃음소리로 GG를 치며) 그러면 우리는 두 방 사이에 통로가 하나 있고 통로마다 단방향으로 통과하는 사람이 7을 넘지 않는다고 상상해도 무방하다.(반증법을 통해 7이 넘으면 반드시 우수하지 않다는 것을 알 수 있다) 그래서 교묘한 상태 디자인이 생겼다. dp[i][j]는 1차적으로 i조 통로를 표시하고 j는 인원수(쌍방향)를 표시한다. 그러면 옮긴 후에 다음 방을 합법적으로 옮길 수 있다면 옮길 수 있다.초기 상태에서 가짜 통로를 정의합니다. 출입은 0입니다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 2147483647
#define LL long long
#define clr(x) memset(x, 0, sizeof x)
#define digit (ch <  '0' || ch >  '9')

using namespace std;

template <class T> inline void read(T &x) {
    int flag = 1; x = 0;
    register char ch = getchar();
    while( digit) { if(ch == '-')  flag = -1; ch = getchar(); }
    while(!digit) { x = (x<<1)+(x<<3)+ch-'0'; ch = getchar(); }
    x *= flag;
}

int n;
LL dp[100020][15],a[100020],ans = INF;

inline bool check(int t) { return (!t || t == 4 || t == 7); }

int main() {
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    memset(dp, 0x3f, sizeof dp); read(n);
    for(register int i = 1; i <= n; i++) read(a[i]);
    dp[0][7] = 0;
    for(register int i = 0; i < n; i++)
        for(register int j = 0; j <= 14; j++) if(dp[i][j] < INF)
            for(register int k = 0; k <= 14; k++) if(check(a[i+1]-j+k))
                dp[i+1][k] = min(dp[i][j]+abs(k-7), dp[i+1][k]);
    for(register int i = 0; i <= 14; i++) if(check(a[n]-i+7)) ans = min(ans, dp[n-1][i]);
    printf(ans >= INF ? "-1" : "%d",ans);
    return 0;
}