买瓜--dfs‘剪枝

1.后缀和剪枝

2.排序大数在前剪枝

3.枚举3种情况

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=2005;
4. typedef long long ll;
5. const double MAX=1e10;
6. int n,m;
7. double a[32];
8. double s[32];
9. int mi=-1;
10. int c=0;
11. void dfs(double w,int d,int x)
12. {
13.         if(w==m)
14.         {
15.                 if(!c) mi=d,c++;
16.                 else mi=min(d,mi);
17.         }
18.         if(w+s[x+1]<m) return;
19.         if(w>m) return;
20.         if(x>n) return;
21.         dfs(w+a[x+1],d,x+1);
22.         dfs(w,d,x+1);
23.         dfs(w+a[x+1]/2,d+1,x+1);
24.        
25. }
26. int main(){
27.         ios::sync_with_stdio(0);
28.         cin.tie(0);
29.         cout.tie(0);
30. cin>>n>>m;
31. for(int i=0;i<n;i++) cin>>a[i];
32. sort(a,a+n,greater<double>());
33. for(int i=n-1;i>=0;i--) s[i]=s[i+1]+a[i];
34. dfs(a[0],0,0);
35. dfs(0,0,0);
36. dfs(a[0]/2,1,0);
37. cout<<mi;
38. return 0;
39. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。