首页 > 代码库 > 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