！80分歪解注意
我一看这题感觉就是搜索啊…前面大佬都是二分，说实话我没想到，题解也没人发搜索的（人家都二分过了谁管你搜索）
后来证实了二分是正解，搜索是歪解…具体什么原因待会会讲
简单分析题意，我们可知对于每一种调料我们都可以选或者不选，选就获得一个收益且付出一个代价，不选就当无事发生
首先想到是背包？但是本题计算最终收益的方法是求和后再商…想了想感觉以我的水平很不可做orz
那就尝试一下搜索列举每种决策吧（我猜有人记不住数组含义，于是贴心的标出来hh
double tim[N],vl[N];//tim是花费时间，vl是价值（好吃程度
void dfs(int k,double cst,double del,int c){
//正在处理第k个，话费时间cst，收益好吃程度del，已经选了c中调料
if(c==m){//选好了m种则更新答案
ans=max(ans,del/cst);
return;
}
if(k>n) return;//选出界了
dfs(k+1,cst+tim[k],del+vl[k],c+1);//选择会带来收益和代价，以及选择数量++ dfs(k+1,cst,del,c);//不选则当无事发生，考虑下一个决策
}测了样例，感觉自己真的很不错，提交一看，80分
毕竟是纯暴力做法..
以下是我对于剪枝的一些思考和失败经历，由于太弱尝试几次并不成功，欢迎神牛指点一下orz
想了想，有一种剪枝策略是
用前缀和数组记下每个调料的收益，在对一个决策进行分析时，如果后面的调料全选也不如当前的状态优，则跳过这个决策
void dfs(int k,double cst,double del,int c){
//正在处理第k个，话费时间cst，收益好吃del，已经选了c
if(cst!=0 && (del+s[n]-s[k-1])/cst<=del/cst)return;
if(c==m){
//cout<<del<<':'<<cst<<endl;
ans=max(ans,del/cst);
return;
}
if(k>n) return;
dfs(k+1,cst+tim[k],del+vl[k],c+1);
dfs(k+1,cst,del,c);
}测了样例，感觉自己真的很不错，交上去测，还是T
orz
其实仔细想想就能知道这种状态过于极端，虽然正确但并不能剪掉能影响算法时间复杂度的枝条，于是我不信邪，后面总不能收益都是1吧，我想牺牲一定的正确率来求能卡进1s时限（什么时候变成调参问题了）
if(cst!=0 && (del+s[n]-s[k-1])/cst<=del/(cst+10000))return;测了样例，感觉自己真的很不错，交上去测，还是T
orz
其实仔细想想就能知道这种状态过于极端，虽然正确但并不能剪掉能影响算法时间复杂度的枝条，于是我不信邪，后面总不能收益都是1吧，我想牺牲一定的正确率来求能卡进1s时限（什么时候变成调参问题了）
if(cst!=0 && (del+s[n]-s[k-1])/cst<=del/(cst+10000))return;剪掉了吗？剪掉了吗？并没有
下载分析数据范围后猛然发现，大数据点的话费都是1w+…那么可以知道这种剪枝策略不可能有效了
再分析一波，似乎可以这么剪一下：
对于一个状态，如果剩下的全选后面收益最大的调料且代价只加一个较小值（又调参草）还不如当前优，则可以不选
分析完发现，似乎可以用 $O(n^2)$ 的效率维护一个区间最值，您想用线段数+期望也行orz，实现这个剪枝，但是经过暴力分析大概可以估计，由于剪枝根本思想没变，效率也没有在时间复杂度上的提升，加之老代码跑完得快1min，于是果断放弃（然而得分的数据点都是2ms，3ms，可见数据水的可以hh）
考场上的话，我就拿部分分滚粗了qwq
以上是我对于本题剪枝的一点点小思考和尝试，如果你有更好的剪枝策略请和我一起讨论，让本题有一个歪解AC吧（笑