网站开发工作计划,做网站做生意,常见的网络营销推广方式有哪些,wordpress怎么发文章这道题用的知识点是DFS剪枝。难的不在DFS上#xff0c;而是在剪枝上如何选择。
思路#xff1a;这道题我们看到是按照字典序排的#xff0c;但是#xff0c;我们注意到#xff0c;看似是全排列的递归#xff0c;实则不是。
我们前面也了解过#xff0c;全排列的数字大…这道题用的知识点是DFS剪枝。难的不在DFS上而是在剪枝上如何选择。
思路这道题我们看到是按照字典序排的但是我们注意到看似是全排列的递归实则不是。
我们前面也了解过全排列的数字大小是没有规则的当然指数型也不可能这并不涉及到选与不选的问题。而且我们看到这些数字有点像升序排列的所以可能会是组合型递归。但是呢我们又发现它们的数字并不是严格单调的而是有相同的数字在里面排序。这怎么办呢
改进方法已经在代码里了就是在进行下一次dfs的时候我们只需要写上i就行而不是i1,如果是i1就会严格单调了。
只是这样写起来会有数据点TLE。这是为什么呢因为有些地方是需要剪枝的。那么这里我们怎么剪枝呢如果你想说在求出来的和不是n的时候剪枝那也是在全部数字枚举出来的时候才会判断的仅仅是这样并不能完全剪枝。那该怎么办呢这里我们直接在循环里剪枝也就是在枚举的过程中进行剪枝。怎么剪枝呢举个例子
当我们n7k4时这个时候假如我们已经列举到13了现在正在第三个位置的dfs当中这个时候按照我们的写法下一个数字肯定是3最后一个数字也是3这是对于自己编写的程序的理解。
我们看如果这几个数字加起来是不是已经超过7了也就是说第四个位置我们根本不需要考虑了前面已经7了后面再加就不行了这里我们直接让循环不去dfs了而是进行下一次循环。这就省了一次dfs函数的调用那么怎么实现这种想法呢
我们在循环中改进循环条件就行这和上几次的剪枝是不一样的这里的剪枝涉及到的是对于在枚举过程中的剪枝而不是对于全部枚举完之后的剪枝这里是不同点。在上面的例子中我们看到其实知道了第三个数字我们也就知道了第四个数字了。所以我们只需要循环到第二个位置后判断后面两个位置的和与前面我们已经计算了的sum相加是不是n就行了这就是优化的地方。
注意这里的dfs有三个变量第一个是位置第二个是从哪个数开始枚举第三个则是累加的数用来记录的。
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includesstream
#includemap
#includelimits.h
#includeset
#define MAX 100010
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
typedef pairint,int PII;
int arr[MAX];
LL n, m, counts, num;
void dfs(int u,int st,int sum) {if (u m) {if (sumn || sumn)return;else {counts;}return;}for (int i st; sum(m-u1)*i n; i) {arr[u] i;dfs(u 1,i,sumi);arr[u] 0;}}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin n m;dfs(1,1,0);cout counts endl;return 0;
}
