石家庄营销网站建设价格,工作满多少年不能辞退,网推项目平台,上海专业网站建设报题解 暴搜的思路容易想到#xff0c;但是剪枝细节有很多#xff0c;数据很强。 搜索思路#xff1a; a. 用dfs(left_num,left_len,bound)表示当前还需要拼left_num根木棒#xff0c;当前正在拼的木棒还剩left_len长度#xff0c;搜索是从大往小搜索#xff0c;并且当前搜…题解 暴搜的思路容易想到但是剪枝细节有很多数据很强。 搜索思路 a. 用dfs(left_num,left_len,bound)表示当前还需要拼left_num根木棒当前正在拼的木棒还剩left_len长度搜索是从大往小搜索并且当前搜索到了bound位置。 b. 每次拼一根木棒都相当于是从大到小搜索一遍所有可用的小木棒。 剪枝的思路 拼小木棒的时候从大到小枚举。当前枚举的小木棒a[i]如果是拼成一根大木棒的最后一根小木棒但是最后却没有拼成所有的大木棒那么直接从此返回失败。因为如果之后的小木棒组合能拼成所有的大木棒那么可以将a[i]与其中的一些做置换得到等效局面。假设某根大木棒刚要开始枚举剩余要找长度为目标大木棒长度但是没有拼成所有的大木棒那么直接返回失败。因为这表明无法再继续拼成任何一根大木棒了。 4.如果当前拼接长度为a[i]的木棒发生失败那么任何长度等于a[i]的木棒都可以直接跳过。 ##代码
#include iostream
#include algorithm
#include cstdio
#include cstring
using namespace std;
const int maxn 100;
int a[maxn],vis[maxn];
int n,tot,len;
bool dfs(int left_num,int left_len,int bound){//表示剩余要拼left_num根木棒当前再拼的剩余left_len下一个从bound开始if(left_num 0 left_len 0) return true;if(left_len 0){return dfs(left_num-1,len,tot-1);}for(int i bound;i 0;--i){if(vis[i]) continue;if(a[0] left_len) return false;vis[i] 1;if(dfs(left_num,left_len-a[i],i-1)) return true;vis[i] 0;if(left_len - a[i] 0 || left_len len) return false;while(i a[i-1] a[i]) --i;}return false;
}
int main(){scanf(%d,n);int mi 0,sum 0;for(int i 0;i n;i) {int tmp;scanf(%d,tmp);if(tmp 50) continue;a[tot] tmp;sum tmp;mi max(mi,tmp);}sort(a,atot);for(len mi;len sum / 2;len){if(sum % len ! 0) continue;memset(vis,0,sizeof(vis));if(dfs(sum/len,0,0))return 0*printf(%d\n,len);}printf(%d\n,sum);return 0;
}
