HDU 1258 Sum It Up

这题郁闷了,排序过不了,后来仔细想想不用排序, 于是果断删了,没想到删了再杭电能过,在北大不能过,真郁闷了

这题是以简单DFS,在搜到时把结果存起来,然后再暴力搜索,看是否已存在这样的sum,最后一次性输出来就o了.先贴一神代码把.... 这个hdu poj 都能过( 这个算法非常好.以后对于组合问题都能这么干了 )

#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] )//这个就保证如果有相同的数,相同的组合,每个只用一次,而且是第一次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; } 下面这个是我的搓代码( 杭电能过,北大挂了 ) #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; }

转载于:https://www.cnblogs.com/Lvsi/archive/2011/05/04/2037049.html

总结

以上是生活随笔为你收集整理的HDU 1258 Sum It Up的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。