HDU-1258 Sum It Up （DFS）

约定不等于承诺〃 2021-10-19 11:22 185阅读 0赞

题意：输入一个m，和n个数，输出所有数据组合相加和为m的组合，输出的数列不重复；

emmmm....一开始是想dfs全找出来存起来然后去重，然后发现自己数据结构也很菜，实现不了，看了大佬的博客换新思路；这个题让我对dfs更懂了一些。

**解释无能...直接上代码加注释**

#include<algorithm>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    
    int a[100100],b[100100];
    int flag,n,m;
    
    void dfs(int len,int k,int sheng)
    {
        if(sheng==0){            //如果剩的等于0就把数组输出 
            flag=0;
            for(int j=0;j<len;j++){
                if(j) printf("+");
                printf("%d",b[j]);
            }
            printf("\n");
            return ;
        }
        for(int i=k;i<n;i++){
            if(i==k||a[i]!=a[i-1]&&sheng-a[i]>=0){   //一开始还想为啥不用考虑行里重复（队友大佬给我解释了一下秒懂） dfs是一行一行的扫每行选一个 所以不会重     
        //去重 比如he=100 50 50 50 25 25 25 在dfs到k==3的时候搜索到了有25的情况（50 25 25） 首位为25的就不在搜索了
                b[len]=a[i];            //符合条件就存到数组里； 
                dfs(len+1,i+1,sheng-a[i]);
            }
        }
    }
    
    int main()
    {
        while(scanf("%d%d",&m,&n)&&(m||n)){
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            flag=1;
            printf("Sums of %d:\n",m);
            dfs(0,0,m);
            if(flag) printf("NONE\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/lilibuxiangtle/p/11317999.html

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 Sum It Up

Sum It Up Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

谁借莪１个温暖的怀抱￠/ 2024年02月18日 23:13/ 0 赞/ 38 阅读

相关 HDU 1172(dfs)

题意：如题。 include <cstdio> include <cstdlib> include <cmath> include

亦凉/ 2022年09月20日 11:23/ 0 赞/ 106 阅读

相关 hdu1258（DFS）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1258 思路：根据题意：输出应该是从大到小的，所以先排序 1. 将数组排序

我会带着你远行/ 2022年09月18日 10:45/ 0 赞/ 229 阅读

相关 HDU--Max Sum

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

小咪咪/ 2022年08月26日 05:52/ 0 赞/ 11 阅读

相关 HDU 4407 Sum

这题一开始以为是什么数据结构，但是确实没想到什么东西维护和一个变化的互质的东西。但是如果是容斥就可以做，对于无修改的数列，和p互质的数的累加。但是因为各种操作数最大为10

分手后的思念是犯贱/ 2022年08月05日 08:26/ 0 赞/ 126 阅读

相关 HDU 1258 Sum It Up （dfs+去重）

Sum It Up Problem Description Given a specified total t and a list of n integers, fin

悠悠/ 2022年06月13日 07:50/ 0 赞/ 148 阅读

相关 Sum It Up

Sum It Up Problem Description Given a specified total t and a list of n integers, f

阳光穿透心脏的1/2处/ 2022年05月16日 11:21/ 0 赞/ 117 阅读

相关 DFS-HDU 1258-Sum It Up

DFS-HDU 1258-Sum It Up -------------------- 题目链接：[Sum It Up][] 思路：题目

Love The Way You Lie/ 2022年05月15日 01:19/ 0 赞/ 123 阅读

相关 Sum It Up ( dfs ➕ 去重)

Problem Description Given a specified total t and a list of n integers, find all distin

港控/mmm°/ 2021年11月10日 12:46/ 0 赞/ 193 阅读

相关 HDU-1258 Sum It Up （DFS）

题意：输入一个m，和n个数，输出所有数据组合相加和为m的组合，输出的数列不重复； emmmm....一开始是想dfs全找出来存起来然后去重，然后发现自己数据结构也很菜，实现不

约定不等于承诺〃/ 2021年10月19日 11:22/ 0 赞/ 186 阅读