救救我吧。除了超时,还有哪里逻辑错了。
查看原帖
救救我吧。除了超时,还有哪里逻辑错了。
99032
gauss楼主2021/9/21 16:41

答案提示除了超时还有部分结果错误。想知道的哪里错了。有大神可以指出来吗。下面是我的代码:

#include <bits/stdc++.h>

using namespace std;

int bac[50] = {0};
int need[1000] = {0};
int ans = 0;

void DFS(int step, int cnt, int m, int n) {
    /***
     * step: 指定按照哪一块需要的模板进行分割,即need的下标
     * cnt: 统计当前状态已经有多少想要的木板了
     * m: bac数组的长度,即店老板有的木板规格
     * n: need数组的长度,即需要的木板的规格
     */
    if (step == n) {
        ans = max(ans, cnt);
        return;
    }
    for (int i = 0; i < m; ++i) {
        if (bac[i] > need[step]) {
            bac[i] -= need[step];
            DFS(step + 1, cnt + 1, m, n);
            bac[i] += need[step];
        }
        DFS(step + 1, cnt, m, n);
    }
}

int main() {
    int m;
    int n;

//    while (scanf("%d", &m) != EOF) {
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d", &bac[i]);
        }

        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &need[i]);
        }

        ans = 0;
        DFS(0, 0, m, n);
        printf("%d\n", ans);
//    }

    return 0;
}

2021/9/21 16:41
加载中...