厄运的袋子
用到了深度遍历 递归回溯法
这里假设一个例子： 1 1 1 2 2 3 4 5 7 8
因为要确认是否辛运，并且保持这次不幸运，那么下一次不可能辛运，所以需要先排序
虽然排序会减少效率，但此次排序正是为了更好的效率，而排序的 假设
主要思路：
主要思路都在图和动图里了。最后附上代码
#include#include #include using namespace std; //数据 个数 位置 和 积 int summ(vector<int>& x,int n,int pos,int sum,int multi) { int count=0; for(int i=pos;i ) { sum+=x[i]; multi*=x[i]; if(sum>multi) { count+=1+summ(x,n,i+1,sum,multi);//如果辛运 就往下一个数加 } else if(x[i]==1) { count+=summ(x,n,i+1,sum,multi);//不幸运时 如果是1 不影响结果 需要继续往下加 } else { break;//不幸运 并且不是1 说明已经结束 因为排序过 这次不幸运 那么接下来可不能幸运 } //结束回退 回退到最开始 然后从第i+1个位置开始 当开头 sum-=x[i]; multi/=x[i]; //因为可能开头下去都是重复的 重复的不影响结果 所以需要找到不同的开头 while(i ;i++1&&x[i]==x[i+1]) { i++; } } return count; } int main() { int n; cin>>n; vector<int> v(n); for(int i=0;i ) { cin>>v[i]; } sort(v.begin(),v.end());//排序的目的 是为了提高效率 cout< ;i++0,0,1); return 0; } (v,n,
Original: https://www.cnblogs.com/LonelyMoNan/p/16737585.html
Author: lemon-Breeze
Title: 幸运的袋子 附加动图演示！
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/607411/
转载文章受原作者版权保护。转载请注明原作者出处！