10476 좁은 미술전시관

백준 10476 좁은 미술전시관 https://www.acmicpc.net/problem/10476

N*2의 가치가 매겨진 방이있는 미술관이 있다. 방은 닫을 수 있되 길이 유지되도록 닫아야한다. 
K개의 방을 닫을 때 닫히지 않은 방의 최대 가치를 구하는 문제이다.

이게 뭐라고 2시간정도 잡아먹은듯 하다.
N행에서의 방의 모습은 3가지 경우 뿐이다. (□열림, ■닫힘) 
F = 0 : ■□ (왼쪽만 닫힘) 
F = 1 : □■ (오른쪽만 닫힘)
F = 2 : □□ (닫히지 않음)

F가 0인 경우에서 N-1행은 0이나 2의 F형태가 와야한다.
F가 1인 경우에서 N-1행은 1이나 2의 F형태가 와야한다.
F가 2인 경우에서는 3가지 형태 모두 가능하다.

이러한 틀로 점화식을 유도 할 수 있다.

$DP[N][K][F] $ : N행까지 방을 K개 닫고 N행이 F인 모습일때 닫히지 않은 방들의 가치의 최대합

$DP[N][K][0] : max(DP[N-1][K-1][0], DP[N-1][K-1][2]) + map[N][1]$
$DP[N][K][1] : max(DP[N-1][K-1][1], DP[N-1][K-1][2]) + map[N][0]$
$DP[N][K][2] : max(DP[N-1][K][0], DP[N-1][K][1], DP[N-1][K][2]) + map[N][0] + map[N][1]$

#include <cstdio> #include <algorithm> using namespace std; #define tmax(a,b,c) max(a,max(b,c)) int N, K; int map[201][2]; int dp[202][202][3]; int main(){     int a,b;     scanf("%d%d", &N, &K);     for (int n = 1; n <= N; n++)         scanf("%d%d", &map[n][0], &map[n][1]);     scanf("%d%d", &a, &b);         dp[1][1][0] = map[1][1];     dp[1][1][1] = map[1][0];     dp[1][0][2] = map[1][1] + map[1][0];       for (int n = 2; n <= N; n++){         for (int k = 0; k <= K; k++){             if (k >= 1){                 dp[n][k][0] = max(dp[n - 1][k - 1][0], dp[n - 1][k - 1][2]) + map[n][1];                 dp[n][k][1] = max(dp[n - 1][k - 1][1], dp[n - 1][k - 1][2]) + map[n][0];             }             if (n != k)                 dp[n][k][2] = tmax(dp[n - 1][k][0], dp[n - 1][k][1], dp[n - 1][k][2]) + map[n][0] + map[n][1];         }     }     printf("%d\n", tmax(dp[N][K][0], dp[N][K][1], dp[N][K][2]));     return 0; } Colored by Color Scripter

cs