首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Poj 1564 || HDU 1258 Sum It Up(dfs+技巧)

Poj 1564 || HDU 1258 Sum It Up(dfs+技巧)

作者头像
Ch_Zaqdt
发布2019-01-10 14:38:12
3700
发布2019-01-10 14:38:12
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

      题意就是先输入n,m,然后输入m个数,问在这m个数里有多少种任意相加起来等于n的方法,并且输出这些相加的数。

      首先在进行dfs前我们可以把前面那些大于n的数省掉,比如说n是3,m个数为6,5,4,3,2,1,那么我们可以直接从第4个数开始进行dfs。然后在搜索到一种满足sum等于n的情况时, 我们需要有一个去重的操作(直接看代码吧)。

AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int pre[10005];
int ans[10005];
int n,m;
int flag;
int num;

void Output(){
  printf("%d",ans[0]);
  for(int i=1;i<num;i++){
    printf("+%d",ans[i]);
  }
  printf("\n");
}

void dfs(int x,int sum){
  if(sum == n){
    Output();
    flag = 1;
    return ;
  }
  if(sum > n)return ;
  for(int i=x;i<m;i++){
    ans[num++] = pre[i];
    dfs(i + 1,sum + pre[i]);
    num--;
    while(i+1<m&&pre[i]==pre[i+1])i++;     // 去重
  }
}

int main()
{
  while(scanf("%d%d",&n,&m)){
    if(!n && !m) break;
    for(int i=0;i<m;i++)scanf("%d",&pre[i]);
    flag = 0;
    num = 0;
    int temp;
    for(int i=0;i<m;i++){
      if(pre[i] <= n){
        temp = i;
        break;
      }
    }
    printf("Sums of %d:\n",n);
    dfs(temp,0);
    if(flag == 0)printf("NONE\n");
  }
  return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年03月17日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档