首页 > 代码库 > ecnu 1244
ecnu 1244
顺序可略,多阶段决策,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; }
ecnu 1244
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。