虽然我很懒，但集训期间还是强迫我自己写一下博客吧！
搜索剪枝
不搜不知道，我的搜索如同一坨shift。
搜索没逻辑，剪枝随便捡，然后喜提 with return value 3221225725
P1025数的划分
非常简单的一道，数的拆分题
题目描述
将整数 \(n\) 分成 \(k\) 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：\(n=7\)，\(k=3\)，下面三种分法被认为是相同的。
\(1,1,5\);
\(1,5,1\);
\(5,1,1\).
问有多少种不同的分法。
为了防止重复，很明显我们要保证后一个数大于等于前一个数，另外判断一下剩下的n除以剩下的个数，是不是大于等于这个数。
void finding(int minn,int kn,int rn){
if(kn==1&&rn>=minn){
ans++;
return ;
}
for(int i=minn;i<=n;i++){
if(rn-i>=0&&(double)(rn-i)/(kn-1)>=minn) finding(i,kn-1,rn-i);
}
return ;
}
P1120 小木棍
哇，这题苦战两小时，没结果，就先放一放。一想头就炸，有点恐怖。
又经过一个小时苦苦挣扎，分数最高终于来到了81（哭死
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 \(50\)。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
对于全部测试点，\(1 \leq n \leq 65\)，\(1 \leq a_i \leq 50\)。
解题思路
这道题最麻烦的是我要用一堆数，拼凑出几个大小相同的数，至于到底是几个呢不知道。
不过由于这些木棍必须刚好用完，所以最短就是最长的木棍，最长就是所有木棍的和。
所以枚举我的目标木棍长度，然后暴力枚举拼凑，然后理所当然就要剪枝。
先把我的78分代码放这吧，思路很明了，但剪枝优化还不够
#include<bits/stdc++.h>
using namespace std;
int n,a[100],cnt,ans,sum,maxn,len;
int nex[100];
bool vis[100];
bool cmp(int x,int y){
return x>y;
}
bool check(int stick,int cab,int last){//stick表示当前正在凑第几根木棒
if(stick>cnt) return 1; //cab表示正在凑的这根木棒已经凑了多长
if(cab==len) return check(stick+1,0,1);//last表示最后使用的小木棒标号
for(int i=last;i<=n;i++){
if(!vis[i]&&cab+a[i]<=len){
vis[i]=1;
if(check(stick,cab+a[i],i+1)) return 1;
vis[i]=0;
if(cab==0) return 0;
i=nex[i];
}
}
return 0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
maxn=max(maxn,a[i]);
sum+=a[i];
}
ans=sum;
sort(a+1,a+1+n,cmp);
int now=n;
nex[n]=n;
for(int i=n-1;i>=1;i--){
if(a[i]!=a[i+1]){
now=i;
}
nex[i]=now;
}
for(int i=maxn;i<=sum;i++){
if(sum%i!=0) continue;
cnt=sum/i;
len=i;
memset(vis,0,sizeof(vis));
if(check(1,0,1)){
ans=i;
break;
}
}
printf("%d",ans);
return 0;
}