zoj 2059 - The Twin Towers
來源：程序員人生 發布時間：2014-10-03 08:00:00 閱讀次數：1927次
題目：給你一些磚塊，問你是否能羅列成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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
