ecnu 1244

SERCOI 近期设计了一种积木游戏。每一个游戏者有N块编号依次为1 ，2，…，N的长方体积木。

对于每块积木,它的三条不同的边分别称为”a边”、“b边”和”c边”。

游戏规则例如以下：

1. 从N块积木中选出若干块，并将它们分成M（l<=M<=N）堆，称为第1堆。第2 堆…。第M堆。

每堆至少有1块积木。而且第K堆中随意一块积木的编号要大于第K+1堆中随意一块积木的编号(2<=K<=M)。

2. 对于每一堆积木,游戏者要将它们垂直摞成一根柱子,并要求满足以下两个条件：

（a）. 除最顶上的一块积木外。随意一块积木的上表面同且仅同还有一块积木的下表面接触，

而且要求以下的积木的上表面能包括上面的积木的下表面，

也就是说。要求以下的积木的上表面的两对边的长度分别大于等于上面的积木的两对边的长度。

（b）. 对于随意两块上下表面相接触的积木，以下的积木的编号要小于上面的积木的编号。

最后。依据每人所摞成的M根柱子的高度之和来决出胜负。

请你编一程序，寻找一种摞积木的方案，使得你所摞成的M根柱子的高度之和最大。

思路：

顺序可略。多阶段决策

DP[col][used][top][face]代表在第 col 柱时。已经用了 used 个方块，第 col 上面是第 top 块的 face 面

1.当前木块放在第col上面。2.当前木块另起col。3.舍弃

#include <iostream>
#include <cstring>
using namespace std;

struct Block{
    int lens[3];
};

Block blocks[110];
int DP[110][110][110][3];

int M, N;


int judge( int bellow, int f1, int up, int f2 ){

    int bellow_a = blocks[bellow].lens[f1];
    int bellow_b = blocks[bellow].lens[( f1 + 1 ) % 3];
    int up_a     = blocks[up].lens[f2];
    int up_b     = blocks[up].lens[( f2 + 1 ) % 3];

    if( ( up_a <= bellow_a && up_b <= bellow_b ) ||
        ( up_a <= bellow_b && up_b <= bellow_a ) )
        return blocks[up].lens[( f2 + 2 ) % 3];

    return 0;
}


int res_search( int col , int used, int top, int face ){

    if( DP[col][used][top][face] )
        return DP[col][used][top][face];

    if( col == M && used == N )
        return 0;

    if( col != M && used == N )
        return -1;

    int res = 0;

    if( col ){
        for( int f = 0; f <= 2; ++f ){

            int ok = judge( top, face, used + 1, f );

            if( ok )
                res = max( res, res_search( col, used + 1, used + 1, f ) + ok );

        }
    }

    if( col < M ){
        for( int f = 0; f <= 2; ++f ){
            res = max( res, res_search( col + 1, used + 1, used + 1, f ) + blocks[used + 1].lens[( f + 2 ) % 3] );
        }
    }

    res = max( res, res_search( col, used + 1, top, face ) );
    DP[col][used][top][face] = res;

    return res;

}


int main(){

    while( cin >> N >> M ){

        for( int i = 1; i <= N; ++i ){
            cin >> blocks[i].lens[0] >> blocks[i].lens[1] >> blocks[i].lens[2];
        }

        memset( DP, 0, sizeof( DP ) );

        int res = res_search( 0, 0, 0, 0 );

        cout << res << endl;
    }

    return 0;
}