這題郁悶了,排序過不了,后來仔細(xì)想想不用排序, 于是果斷刪了,沒想到刪了再杭電能過,在北大不能過,真郁悶了

這題是以簡(jiǎn)單DFS,在搜到時(shí)把結(jié)果存起來,然后再暴力搜索,看是否已存在這樣的sum,最后一次性輸出來就o了.先貼一神代碼把.... 這個(gè)hdu poj 都能過( 這個(gè)算法非常好.以后對(duì)于組合問題都能這么干了 )

#include<stdio.h> int t,n,num[20],flag,res[20]; void DFS( int p,int s,int nu ) {if( s == t ){flag = 1;for( int i = 0; i < nu; ++i )printf( i == 0 ? "%d" : "+%d",res[i] );puts( "" );return ;}for( int i = p; i < n ; ++i ){if( i > p && num[i] == num[i-1] )//這個(gè)就保證如果有相同的數(shù),相同的組合,每個(gè)只用一次,而且是第一次continue;if( num[i] + s <= t )res[nu] = num[i],DFS( i+1,s + num[i],nu + 1 );}} int main( ) {while( scanf( "%d%d",&t,&n ),t ){flag = 0;for( int i = 0; i < n; ++i )scanf( "%d",&num[i] );printf( "Sums of %d:\n",t );DFS( 0,0,0 );if( !flag )puts( "NONE" );}return 0; } 下面這個(gè)是我的搓代碼( 杭電能過,北大掛了 ) #include<stdio.h> #include<string.h> int des[20],t,n,num[20],c,nu[20]; char ch[20][20]; void DFS( int x,int min ) {if( nu[x] == t ){int i ;for( i = 0; i < x; ++i )ch[c][i] = nu[i+1] - nu[i];ch[c][i] = 0;int f = 1;for( int i = 0; i < c; ++i )if( strcmp( ch[i],ch[c] ) == 0 ){f = 0;break;}if( f )++c;return ;}else{for( int i = min; i < n; ++i ){if( !des[i] )if( nu[x] + num[i] <= t ){des[i] = 1;nu[x+1] = num[i] + nu[x];DFS( x + 1,i );des[i] = 0;}}}} int cmp( char str1[],char str2[] ) {int len1 = strlen( str1 ),len2 = strlen( str2 );if( len1 != len2 )return len1 - len2;return strcmp( str2,str1 ); } int main( ) {while( scanf( "%d%d",&t,&n ) , n ){c = 0;for( int i = 0; i < n; ++i )scanf( "%d",&num[i] ),des[i] = 0;nu[0] = 0;DFS( 0,0 );printf( "Sums of %d:\n",t );if( !c || !t ){puts( "NONE" );continue;}for( int i = 0; i < c; ++i ){for( int j = 0; j < strlen( ch[i] );++j )printf( j == 0 ?"%d": "+%d",ch[i][j] );puts( "" );}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Lvsi/archive/2011/05/04/2037049.html

總結(jié)

以上是生活随笔為你收集整理的HDU 1258 Sum It Up的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。