DFS剪枝算法经典题目-挑选

4954. 挑选 - AcWing题库

给定一个包含 n 个正整数 a1,a2,…,an的集合。

集合中可能存在数值相同的元素。

请你从集合中挑选一些元素，要求同时满足以下所有条件：

1. 被选中元素不少于 2 个。
2. 所有被选中元素之和不小于 l 且不大于 r。
3. 所有被选中元素之中最大元素与最小元素之差不小于 x。

请问，一共有多少种不同的选法。

注意：

• 不考虑元素顺序，{a1,a2} 和 {a2,a1} 应当视为同一种选法。
• 不同元素即使数值相同，也应当视为不同个体，即使 a1=a2，{a1,a3}和 {a2,a3} 也应当视为不同选法。

输入格式

第一行包含四个整数 n,l,r,x。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示不同选法的数量。

数据范围

前 33 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤15，1≤l≤r≤109，1≤x≤106，1≤ai≤106。

输入样例1：

3 5 6 1
1 2 3

输出样例1：

2

输入样例2：

4 40 50 10
10 20 30 25

输出样例2：

2

输入样例3：

5 25 35 10
10 10 20 10 20

输出样例3：

6

根据题目，因为不考虑选取的顺序，所以可以根据下标进行dfs，类似根据下标求组合数。

 首先遍历数组，从每一个数开始dfs，参数分别为当前搜索的数的总和，搜索到的数组的下标，搜索数中最大值，搜索数种最小值，搜索数的个数，然后每次dfs的时候，判断当前总数是否大于 r ，如果大于则不用继续搜索了，可以直接剪掉。然后通过参数判断是否符合条件，如果符合则ans++，然后继续遍历，从index+1开始遍历，更新参数继续dfs，最终结果就为ans。

AC code:

#include<bits/stdc++.h>
using namespace std;
int n, l, r, x;
int arr[20];
int ans = 0;
void dfs(int total, int index, int mx, int mi, int cnt) {if (total > r ) return ;if (total >= l && total <= r && (mx - mi) >= x && cnt > 1) ans++;for (int i = index + 1; i <= n; i++) {int a = max(mx, arr[i]);int b = min(mi, arr[i]);dfs(total + arr[i], i, a, b, cnt + 1);}
}
int main() {cin >> n >> l >> r >> x;for (int i = 1; i <= n; i++) cin >> arr[i];for (int i = 1; i <= n; i++) {dfs(arr[i], i, arr[i], arr[i], 1);}cout << ans;
}