HDU 1258(dfs)

雨点打透心脏的1/2处 2022-09-20 12:41 19阅读 0赞

题意：给出t，n，还有n个非递增的正整数，求用这些非递增的正整数中挑选出可以相加成t的组合。

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    int num[101];
    int amount[101];
    int box[13];
    bool done;
    void DFS(int sum, int end, int sub, int start)
    {
        if (sub > 12)
            return;
        if (sum == 0)
        {
            done = true;
            printf("%d", box[1]);
            for (int j = 2; j < sub; ++j)
                printf("+%d", box[j]);
            printf("\n");
            return;
        }
        for (int j = start; j <= end; ++j)
        {
            if (amount[j])
            {
                if (sum >= num[j])
                {
                    --amount[j];
                    box[sub] = num[j];
                    DFS(sum-num[j], end, sub+1, j);
                    ++amount[j];
                }
            }
        }
    }
    
    int main()
    {
        int t, n, i, tmp, s;
        num[0] = 0;
        while (scanf("%d%d", &t, &n) != EOF && t + n)
        {
            s = i = 0;
            done = false;
            memset(amount, 0, sizeof amount);
            while (n--)
            {
                scanf("%d", &tmp);
                if (tmp > t) continue;
                s += tmp;
                if (tmp != num[i])
                {
                    num[++i] = tmp;
                    ++amount[i];
                }
                else ++amount[i];
            }
            printf("Sums of %d:\n", t);
            if (i == 0 || s < t)
            {
                printf("NONE\n");
                continue;
            }
            DFS(t, i, 1, 1);
            if (!done) printf("NONE\n");
        }
        return 0;
    }