对于网站反爬虫如何做,wordpress+调用+编辑器,asp.net 做网站好吗,网页设计网站制作一般多少钱蓝桥杯2023年第十四届省赛真题-买瓜 该如何剪枝呢#xff1f;⭐⭐
如果当前方案的切的刀数#xff0c;已经大于等于了之前已知合法方案的最优解#xff0c;那么就没必要 往后搜了。如果后面的瓜的总和加起来#xff0c;再加上当前已有的重量#xff0c;都不到m,那么也没…蓝桥杯2023年第十四届省赛真题-买瓜 该如何剪枝呢⭐⭐
如果当前方案的切的刀数已经大于等于了之前已知合法方案的最优解那么就没必要 往后搜了。如果后面的瓜的总和加起来再加上当前已有的重量都不到m,那么也没有必要搜索了。如果你当前已有的重量超过了m,那么说明当前方案非法直接return就好了。n个瓜遍历结束你肯定要return。我们将瓜从大到小排序这是一个贪心。
这个代码有可能超时
#include iostream
#includebits/stdc.h
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int N100;
double a[N];
double s[N];
int n,m;
int ansINF;当前合法方案的最小值。
void dfs(int u,double w,int cnt){if(wm){ansmin(ans,cnt);return;}//剪枝//如果n个瓜都遍历完了那就返回。if(un)return;//如果当前方案并不优于已有的合法答案那就返回。if(cntans)return;//如果总重量已经超了那么当前方案不合法。if(wm)return;//如果后面的瓜所有重量加起来都小于m则当前方案不合法。if(ws[u]m)return;//选但不切dfs(u1,wa[u],cnt);//选切dfs(u1,wa[u]/2.0,cnt1);//不选dfs(u1,w,cnt);
}
bool cmp(int x,int y){return xy;
}
void solve(){cinnm;for(int i0;in;i){cina[i];}sort(a,an,cmp);//后缀和for(int in-1;i0;i--){s[i]s[i1]a[i];}dfs(0,0.0,0);if(ansINF)ans-1;coutansendl;}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--)solve();
}进一步优化 使用双向dfs
