网站建设在国内外有何趋势,农产品网站开发背景,wordpress人工智能,保定百度推广优化排名题目链接#xff1a;P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入#xff1a;
9
5 2 1 5 2 1 5 2 1
样例输出#xff1a;
6
分析#xff1a;这道题一看数据范围就知道是搜索#xff0c;但关键是需要剪枝。
首先我们求出所有木棍的长度和P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入
9
5 2 1 5 2 1 5 2 1
样例输出
6
分析这道题一看数据范围就知道是搜索但关键是需要剪枝。
首先我们求出所有木棍的长度和那么原始木棍的长度一定是长度和的因子这是显然的然后我们就开始对每个因子进行从小到大搜索。
根据贪心性质我们可以知道优先选用长的木棍进行组装因为短的木棍在任何情况下都可以替换等长的长的木棍但是长的木棍在有些情况下无法替换短的木棍所以我们首先要对木棍进行从大到小排序。
先来看一下搜索函数的参数假如我们要枚举的长度是len首先需要知道当前长度为len的木棍还差多少也就是res然后还需要知道组成当前木棍的上一节子棍的长度last因为我们枚举的子棍是逐渐减少的所以这个可以用于剪枝最后一个就是当前我们还差几根长度为len的木棍就可以完整拼完了。
下面来分析一下哪些地方可以剪枝
1.如果我们一开始拼一节长度为len的木棍这个时候还没有放上去小木棍那么这个时候我们就放上去还未使用过的长度最长的木棍。因为所有木棍最后都一定要用上的
2.我们可以用nx[i]标记下一个与第i根木棍长度不一致的编号假如我们当前用第i根木棍没有拼接成功那么如果下一根木棍跟当前木棍长度一样那么我们也就没有必要用下一根木棍了直接选用下一个跟当前木棍长度不一致的木棍即可
3.我们记录了组装当前木棍的剩余长度res和组成当前木棍的上一个子木棍last那么我们下一根木棍的长度一定是小于等于两者的较小值的查询第一个小于等于两者较小值的木棍我们可以用二分来查找
4.根据第一条剪枝我们可以知道假如当前木棍还没有开始拼我们优先选择未使用过且最长的木棍来进行拼接但是如果拼接失败那么我们没必要用更小的木棍去尝试拼接直接返回false即可如果要是剩余的长度等于当前木棍的长度而且还未拼接成功这就代表着我们在组装当前木棍时选取最合适子木棍依旧无法拼接成功那么这个时候我们也是直接返回false即可。
加上上面四个剪枝就可以ac了
细节见代码
#includecstdio
#includeiostream
#includealgorithm
#includecstring
#includemap
#includequeue
#includevector
#includecmath
using namespace std;
const int N100;
int a[N],len;
bool vis[N];
int nx[N];
bool cmp(int a,int b)
{return ab;
}
int n;
bool dfs(int res,int last,int cnt)//res记录当前这根木棍还剩的拼接长度last记录拼接当前木棍的上一个木棍的长度cnt记录还剩多少个木棍
{if(res0){if(cnt1) return true;for(int i2;in;i)//选择第一个没有被使用的木棍进行拼接 {if(vis[i]) continue;vis[i]true;if(dfs(len-a[i],a[i],cnt-1)) return true;vis[i]false;break;}}int l1,rn;int tmin(last,res);while(lr)//二分找第一个可以填的位置,下一个子棍的长度一定小于等于上一根拼接该木棍的子棍长度 {int midlr1;if(a[mid]t) rmid;else lmid1;} for(int il;in;i){if(vis[i]) continue;vis[i]true;bool flagdfs(res-a[i],a[i],cnt);vis[i]false;if(flag) return true;//有一个可以了就可以退出了 if(resa[i]||reslen) return false; inx[i]-1;//用第i根木棍没有拼接成功 }return false;
}
int main()
{cinn;int sum0;for(int i1;in;i){scanf(%d,a[i]);suma[i];}sort(a1,an1,cmp);nx[n]n1;for(int in-1;i1;i--){if(a[i]a[i1]) nx[i]nx[i1];else nx[i]i1;}int anssum;for(lena[1];lensum/2;len)//枚举原始木棍长度{if(sum%len) continue;vis[1]true;if(dfs(len-a[1],a[1],sum/len)){anslen;break;}}printf(%d,ans);return 0;
}
