hdoj 1258 SUM IT UP

系统 1852 0
  

程序的思想是:输入数据是,先使用快排对其从大到小进行排序,然后记录相同数据的个数,比如4 3 3 2 2 1 1,最后的数据变成4 3 2 1 ,并且同时数据的个数f[]变成1 2 2 2

然后就是遍历,相同的数据如果不能得到最后的结果,下一次就不会遍历。

 

//剪枝有这几个

首先:从大到小排序,剪枝1

再者:如果当前的sum比要遍历的数据小,则跳过这个数据

 

利用一个vector来记录结果

 

    #include <iostream>

//#include <fstream>

#include <vector>

#include <algorithm>

using namespace std;

/*0MS	344K*/

//function

int cmp(const void *a,const void *b);

void dfs(int index,int sum);



//var

int a[13];       //输入数据 

int b[13];       //记录从大到小的数据,相同数据个数记录在f[]中 

int l;           //b[]数据的长度 

int f[13];        //记录当前数据b[]的个数

vector<int> c; //结果   

bool flag;

//fstream fin;

int main()

{

    //fin.open("1258.txt",ios::in);

    int t,n;

    while(cin>>t>>n&&n!=0)

    {

        flag=false;

        for(int i=0;i<n;i++)

        {

            cin>>a[i];

        }

        memset(f,0,sizeof(f));    

        qsort(a,n,sizeof(a[0]),cmp);

        //把相同的数据合并在一起 

        int cur=a[0]; //当前数据是多少 

        int j=0;

        b[j]=cur;

        for(int i=0;i<n;i++)

        {

              if(a[i]==cur)

                 f[j]++;

              else

              {

                   cur=a[i];

                   b[++j]=cur;

                   i--;

              }    

        }

        l=++j;



        cout<<"Sums of "<<t<<":"<<endl;

        dfs(0,t); 

        if(!flag)

           cout<<"NONE"<<endl;

    }

    system("pause");

    return 0;

}





void dfs(int index,int sum)

{

   if(sum==0)

    {

        flag=true;

        int length=c.size();

        for(int i=0;i<length-1;i++)

            cout<<c[i]<<"+";

        cout<<c[length-1]<<endl;

    }

    else

    {

        for(int i=index;i<l;i++)

        {

            if(b[i]>sum) continue;//剪枝 

            else

            {   

                c.push_back(b[i]);

                f[i]--;

                if(f[i]==0)

                  dfs(i+1,sum-b[i]);

                else if(f[i]>0)

                  dfs(i,sum-b[i]);

                f[i]++; 

                c.pop_back();  

            }            

        }

    }

}



int cmp(const void *a,const void *b)

{

    return ((*(int *)b)-(*(int *)a));

}
  


 

 

hdoj 1258 SUM IT UP


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论