奇奇怪怪的鬼畜剪枝

这种~~鬼畜~~奇怪的剪枝是我在做P1120小木棍时发现的，当时发现前只有78分。

```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int a[70],n,len,t,vl[70],sum,mx,bg;
void dfs(int now,int cnt,int last){
	if(cnt==t-1){
		cout<<len;
		exit(0);
	}
	int mn=-1;
	rep(i,last,mx+1)
	    if(vl[i])mn=i;
	if(mn>len-now)return ;
	bg++;
	REP(i,mx,last){
		if(vl[i]==0 or now+1>len)continue;
		if(now+i==len){
			vl[i]--;
			dfs(0,cnt+1,1);
			vl[i]++;
		    return ;
		}
		if(now+i<len){
			vl[i]--;
			dfs(now+i,cnt,i);
			vl[i]++;
	    }
	}
}
int main(){
	cin>>n;
	rep(i,0,n){
		cin>>a[i];
		vl[a[i]]++;
		sum+=a[i];
		mx=max(mx,a[i]);
	}
	rep(i,mx,sum/2+1){
		len=i,t=sum/i;
		if(sum%i==0)dfs(0,0,1);
	}
	cout<<sum;
}
```

look this。搜索的那个mn变量其实是目前的max，是的，他看起来是错的但其实是对的。

butttttt!
这还不是最奇怪的。加下来就是今天要介绍的~~奇奇怪怪鬼鬼畜畜好用到尖叫的~~剪枝。当时我用了个can数组，can[i][j]表示在拼好了i组后，这一组拼j的长度的最小木棍使用数量。那么可以在dfs中加上一个dep为当前此组的木棍使用数量。然后边求can边dfs。

都挺正常十八？

我的剪枝is:当前dep<这种状态下最优dep。就直接~~用奶龙之力~~return。一look就是错的。因为目前的木棍数量不能衡量最终能否拼成。那么我直接加上一个：90%的概率执行这个错优化。

然后就收获一个：A+ (B+D)/2=A+C=AC。
然后这个~~优化~~就获得最优解第一页~~垫底~~。
but这种尝试付出了极大代价，我不会告诉你我交了129次。

他不止在这一题管用。去look以下P1074。一开始我的代码写了个dfs。无任何优化75。然后我的第一个优化比较无用：
优先填选择少的，定个序dfs。还是T了

第二个就是鬼畜：d[t]表示填了前t个空白（按之前的定序）的最大分数。鬼畜剪枝方式按上面来。卡了几发概率就过了。不过概率是30%。

## 使用指南：
（本内容由本人生成，仅供参考）
先写一个错的但又不是无可救药的那种剪枝，然后根据样例或下的数据调return概率。（可以先试20%到90%）。如果没AC，那就挑一个分最高的微调。
# 禁忌：
# 这玩意纯属娱乐，不确定性高，赛中千万不要用啊
# 还有，这东西再求方案数时不能用
因为他会过滤一些正确的方案但不会过滤全部。所以在求最优时可用，求方案数会算少。

另外，这个算法有一个小优化。那就是不同的搜索阶段，有不同的return概率。比如前期概率稍大一点，更早剪枝。后期小一点，弥补前期的鲁莽。可以提升一点速度，且错误率只会轻微降低
比如在P1120小木棍中，搜到前一半时，return率98%，后半段89%。

完结散flowers！

正在渲染内容...