大气学校网站模板,无锡企业网站制作需要多少钱,wordpress小说站模板,wordpress做支付题目 样例输出是
6
5
题目中给错了#xff0c;不知道什么时候会改。
思路
--剪枝#xff0c;否则时间复杂度和空间复杂度过大#xff0c;会超时。
--注意有多组测试样例时#xff0c;需要将bool数组重新赋值为false。
--函数类型不是void#xff0c;return语句不能省…题目 样例输出是
6
5
题目中给错了不知道什么时候会改。
思路
--剪枝否则时间复杂度和空间复杂度过大会超时。
--注意有多组测试样例时需要将bool数组重新赋值为false。
--函数类型不是voidreturn语句不能省略
--思路刚开始想的大方向是对的将需要处理的数组排序然后从最大值到总和这个范围内搜索找满足题意的木棍长度但是剪枝这里是一头雾水。剪枝是利用一些条件使得不需要dfs许多重复的情况已经pass掉的就不需要再递归了。看到这一题很容易联想到粘木棍将n个短木棍粘成m个长木棍所不同的是这里的m个长木棍长度都是相同的。我们可以一根一根来粘粘成一根长木棍再粘下一根。那么就需要让此时的长木棍的长度作为参数在递归中传递。这时有三种情况当前长度cur加上选中的短木棍的长度可能等于、大于、小于目标长度l。1如果等于l开始粘下一根长木棍长木棍的根数要1cur设为0验证接下来能不能递归成功如果成功就可以直接返回如果不成功就返回false提前结束递归。验证接下来能不能递归成功就是为了在不成功的情况下提前结束递归。2如果大于l说明选中的短木棍不合适需要继续循环遍历下一个短木棍。没有必要验证了因为肯定会返回false的。3如果小于l说明还没有粘完还需要继续粘也要继续循环遍历下一个短木棍。判断接下来能不能递归成功如果不成功的话并且cur为0返回false。为什么只有在cur为0的时候才返回因为如果当前长度不为0并且拼接接下来的短木棍仍然不成功说明此时选择的短木棍不对需要继续for循环选择下一个合适的短木棍如果当前长度为0但不成功说明在以后的递归中也不可能成功了就直接false。
代码
#include iostream
#include vector
#include algorithm
#include cstring
using namespace std;int n; //短木棍的个数
int l; //长木棍的长度
int num; //长木棍的个数
vectorint v(65);
bool b[65] {false}; bool dfs(int s, int j, int cur){ //遍历小木棍的起始位置拼成的长木棍数目长木棍当前长度 if (j num){return true;}for (int i s; i n; i){if (b[i] true || (i ! 0 v[i] v[i - 1] b[i - 1] false)){continue;} //如果这根木棍已被访问过 或 和上一根没有被访问过的木棍长度相同剪枝。if (cur v[i] l){b[i] true;if (dfs(0, j 1, 0)){return true;} //如果继续深度递归能成功直接返回。 b[i] false;return false; //如果不能成功提前终止。 }if (cur v[i] l){b[i] true;if (dfs(i 1, j, cur v[i])){ //i 1,不是s 1 return true;} //如果继续深度递归能成功直接返回。 b[i] false; if (cur 0){return false;} //不能成功如果当前长度为0说明还没有开始拼接 或 已经拼接成了几根上面的if已经尝试过所有的v[i]了所以不可能成功。如果当前长度不为0还可以尝试接下来的v[i]。 } //如果cur v[i] l那么就需要换下一个v[i]来尝试。 }return false; //不是void类型的不能省略return语句。
}int main(){while (cin n n ! 0){int sum 0;for (int i 0; i n; i){cin v[i];sum v[i];}sort(v.begin(), v.begin() n, greaterint()); //从大到小深度搜索比较好找。for (int i v[0]; i sum; i){if (sum % i 0){memset(b, 0, sizeof(b)); //问题出在这里需要将b数组重置为false因为有多组测试用例 l i;num sum / l;if (dfs(0, 0, 0)){cout l endl;break;}} }}return 0;
}
