首页 > 代码库 > Hdu 1258 Sum It Up
Hdu 1258 Sum It Up
Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=1258
一道可以用Dfs解决的题。输出时要先将字典序大的先输出。我采取了如下思路:
先从第一种数开始,假设这种数的个数为k,则取i(介于k到0)个数,然后在下一种数取一定量的数,然后取下一种数的一定量的数,直至加到题目所要求的和。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int MAXN = 15;int T;int N,kind;int order[MAXN]; // 第i种数有几个int value[MAXN]; // 第i种数的值bool vis[MAXN]; //第i个数用了j次int out[MAXN]; // 各个数的顺序bool flag; //可能出现输入的数的总和大于T,但依旧无答案的情况 如 5 3 2 2 2void Out(int);void Dfs( int next,int lastSum,int otherSum,int exist ) //lastSum表示还需要多少数,exsit表示order[0] -> order[exist-1] 已有数{ //Out( exist ); if( lastSum==0 ) { Out( exist ); return ; } if( next>kind || lastSum<0 || lastSum > otherSum ) return ; int i,j; //vis[i] = true; //pos = i; for( i=order[next];i>=0;i-- ) { for( j=exist;j<exist+i;j++ ) out[j]=value[next]; Dfs( next+1,lastSum-value[next]*i,otherSum-order[next]*value[next],j ); }}void Out( int exist ){ flag = true; int i=1; cout << out[0]; while( i<exist ) { printf("+%d",out[i]); i++; } printf("\n");}int main(){ int i,j; int allSum; int temp, compare; while( scanf("%d%d",&T,&N)!=EOF && N ) { memset( order,0,sizeof(order) ); allSum = kind = 0; scanf("%d",&temp); allSum += temp; compare = temp; kind++; order[kind] ++; value[kind] = temp; for( i=1;i<N;i++ ) { scanf("%d",&temp); allSum += temp; if( temp!=compare ) kind++; compare = temp; order[kind] ++; value[kind] = temp; } cout << "Sums of "<< T << ":" <<endl; if( allSum < T ) { cout << "NONE\n"; continue; } if( T==0 ) // 题目说N为0结束,及可能出现T为0,而N不为0,例如出现 0 3 0 0 0 { for( i=1;i<=kind;i++ ) if( value[i]==0 ) break; if( i!=kind+1 ) { cout << "0\n"; continue; } } flag = false; for( i=order[1];i>=0;i-- ) { for( j=0;j<0+i;j++) out[j]=value[1]; //vis[1] = true; Dfs( 1+1,T-value[1]*i,allSum-value[1]*order[1],j ); } if( !flag ) cout << "NONE\n"; } return 0;}
Hdu 1258 Sum It Up
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。