南七星之家 发表于 2025-3-24 13:08:25

买瓜--dfs‘剪枝

1.后缀和剪枝

2.排序大数在前剪枝

3.枚举3种情况

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
typedef long long ll;
const double MAX=1e10;
int n,m;
double a;
double s;
int mi=-1;
int c=0;
void dfs(double w,int d,int x)
{
        if(w==m)
        {
                if(!c) mi=d,c++;
                else mi=min(d,mi);
        }
        if(w+s<m) return;
        if(w>m) return;
        if(x>n) return;
        dfs(w+a,d,x+1);
        dfs(w,d,x+1);
        dfs(w+a/2,d+1,x+1);
       
}
int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a;
sort(a,a+n,greater<double>());
for(int i=n-1;i>=0;i--) s=s+a;
dfs(a,0,0);
dfs(0,0,0);
dfs(a/2,1,0);
cout<<mi;
return 0;
}

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: 买瓜--dfs‘剪枝