国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > zoj 2059 - The Twin Towers

zoj 2059 - The Twin Towers

来源:程序员人生   发布时间:2014-10-03 08:00:00 阅读次数:1799次

题目:给你一些砖块,问你是否能罗列成2个高度相同的塔,每层一个石头。

分析:dp,双塔问题。和LIS,背包等问题相同,前 i项的最优子问题。 

            状态:f(i,j)为前 i个材料,在两塔差的绝对值为j时的高塔(或者低塔)的高度;

            决策:每次有 3种选择:放在高塔上,放在低塔上,或者不放;

            T = O( sum( h )*n ) { 阶段数*长度总和/2 }。

说明:为了减小内存用辅助数组作为滚动数组使用。 

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define max( a, b ) ((a)>(b)?(a):(b)) int f[ 1001 ]; int t[ 1001 ]; int h[ 101 ]; int main() { int n,s; while ( scanf("%d",&n) != EOF && n != -1 ) { s = 0; for ( int i = 1 ; i <= n ; ++ i ) { scanf("%d",&h[ i ]); s += h[ i ]; } s /= 2; memset( f, 0, sizeof( f ) ); memset( t, 0, sizeof( t ) ); for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 0 ; j <= s ; ++ j ) if ( t[ j ] ) { f[ j+h[ i ] ] = max( t[ j ]+h[ i ], f[ j+h[ i ] ] ); f[ abs(h[ i ]-j) ] = max( max( t[ j ], t[ j ]+h[ i ]-j ), f[ abs(h[ i ]-j) ] ); } f[ h[ i ] ] = max( h[ i ], f[ h[ i ] ] ); for ( int j = 0 ; j <= s ; ++ j ) f[ j ] = max( f[ j ], t[ j ] ); for ( int j = 0 ; j <= s ; ++ j ) t[ j ] = f[ j ]; } if ( f[ 0 ] ) printf("%d ",f[ 0 ]); else printf("Sorry "); } return 0; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生