为什么我没剪枝的dfs能过?
查看原帖
为什么我没剪枝的dfs能过?
527902
天使宝贝楼主2024/3/15 20:23

rt,看到题解里的大佬都说裸dfs不能过,为什么我过了?

#include <bits/stdc++.h>
#define ll long long
#define re register int
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
int n, m, r, a[105], ans;
void dfs(int i, int cnt, int sum)
{
    if (cnt == r)
    {
        if (sum > n)
            ans++;
        return ;
    }
    if (i > m)
        return ;
    dfs(i + 1, cnt + 1, sum + a[i]);
    dfs(i + 1, cnt, sum);
}
int main()
{
    IOS;
    cin >> m >> r >> n;
    for (re i = 1; i <= m; i++)
        cin >> a[i];
    dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}
2024/3/15 20:23
加载中...