NOI 1997 블록 게임(문제풀이 보고서)

아이디어:
1. dp[k][i][j][s]는 앞의 i개의 적목을 k더미로 나누고 첫 번째 k더미의 맨 위에 있는 적목 번호는 j이고 j의 s면은 위로 향한다(s=0, 1, 2).
2. 제i차 적목은 3가지 결정이 있다.
   a. dp[k][i][i][t] = min(dp[k][i-1][j][s]); K더미에 놓기;
   b. dp[k][i][i][t] = min(dp[k-1][i-1][j][s]); 한 무더기 만들기;
   c. dp[k][i][j][s] = dp[k][i-1][j][s]; 참여하지 않음;
3. 위에 놓인 변은 아래에 쌓인 나무의 변보다 작기 때문에 a, b, c변을 작은 것부터 큰 것까지 순서대로 배열하여 판단할 때 더욱 편리하다.
4. 순환 중의 t, s 변수는 상하 적목의 방향을 제어한다.우리는 매번 변의 값을 교환할 때마다 b, c만 비교하여 코드를 더욱 상쾌하게 보일 수 있다.
 

#include <iostream>

#include <algorithm>

using namespace std;



const int MAXN = 110;

int dp[MAXN][MAXN][MAXN][3];

int a[MAXN], b[MAXN], c[MAXN]; // 0 bc, 1 ac, 2 ab



int main() {

    int n, m;

    scanf("%d%d", &n, &m);

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

        scanf("%d%d%d", &a[i], &b[i], &c[i]);

        if (a[i] > b[i]) swap(a[i], b[i]);

        if (b[i] > c[i]) swap(b[i], c[i]);

        if (a[i] > b[i]) swap(a[i], b[i]);

    }

    for (int k = 1; k <= m; k++) {

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

            for (int j = 0; j < i; j++) {

                for (int t = 0; t <= 2; t++) {

                    if (t == 1) swap(b[i], a[i]);

                    if (t == 2) swap(c[i], b[i]), swap(a[i], b[i]);



                    for (int s = 0; s <= 2; s++) {

                        if (s == 1) swap(b[j], a[j]);

                        if (s == 2) swap(c[j], b[j]), swap(a[j], b[j]);



                        if (b[i] <= b[j] && c[i] <= c[j])

                            dp[k][i][i][t] = max(dp[k][i][i][t], dp[k][i-1][j][s] + a[i]);



                        

                        if (s == 2) swap(a[j], b[j]), swap(b[j], c[j]);

                        if (s == 1) swap(b[j], a[j]);



                        dp[k][i][i][t] = max(dp[k][i][i][t], dp[k-1][i-1][j][s] + a[i]);

                        dp[k][i][j][s] = dp[k][i-1][j][s];

                    }

                    if (t == 2) swap(a[i], b[i]), swap(c[i], b[i]);

                    if (t == 1) swap(b[i], a[i]);

                }

            }

        }

    }

    int ans = 0;

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

        for (int s = 0; s <= 2; s++)

            ans = max(ans, dp[m][n][j][s]);

    printf("%d
", ans);

    return 0;

}