[蓝桥杯 2023 省 A] 买瓜 –暴力DFS+剪枝优化

来自洛谷：

暴力思路：

①根据题目，可以知道有三种操作，第一种操作选择这个瓜，第二种操作不选择这个瓜，第三种操作选择这个瓜的一半。我们可以用一个res来记录这三种操作返回的结果，最后在返回这三种操作的最小值。 ②从数据样例中知道，对于第三种操作，在进行切一半操作的时候，数据类型会发生改变，int只能存整数，这样会导致答案错误。因此我们存数据前对数据进行2操作，同时我们的总重量也要 m2。 ③由于本题数据过大，会爆int，我们要用long long 来存。 #include //long long 来存数据 #define int long long using namespace std; const int N = 40; int n, m; int arr[N];//存数据 int w[N]; //后缀和 //x表示枚举瓜 sum 表示当前重量 int dfs(int x, int sum){ if(sum == 2m){ return 0; } //遍历完了所有瓜 if(x > n){ return N; } //当前重量超过总重量 不合法 if(sum > 2m){ return N; } //当前重量+加上当前点后缀和小于总重量 不合法 if(sum + w[x] < 2m){ return N; } //直接选 int res1 = dfs(x+1, sum + arr[x]); //选一半 int res3 = dfs(x+1, sum + arr[x] / 2) +1; //不选 int res2 = dfs(x+1, sum); return min({res1, res2, res3}); } signed main(){ cin » n » m; //在存入数据之前 将数据2 //后续操作不需要使用 double for(int i = 1; i <= n; i++){ int x; cin » x; arr[i] = 2*x; } //将arr数组从大到小排序 sort(arr+1, arr+n+1);reverse(arr+1, arr+n+1); //后缀和 for(int i = n; i >= 1; i–){ w[i] = w[i+1] + arr[i]; } //得到答案 int res = dfs(1, 0); //判断一下 能不能买到总重量恰好为m的瓜 if(res == N){ cout « “-1” « endl; }else{ cout « res « endl; } return 0; }