洛谷 1025.数的划分

这道题用的知识点是DFS+剪枝。难的不在DFS上，而是在剪枝上如何选择。

思路：这道题我们看到是按照字典序排的，但是，我们注意到，看似是全排列的递归，实则不是。

我们前面也了解过，全排列的数字大小是没有规则的，当然指数型也不可能，这并不涉及到选与不选的问题。而且，我们看到，这些数字有点像升序排列的，所以可能会是组合型递归。但是呢，我们又发现，它们的数字并不是严格单调的，而是有相同的数字在里面排序。这怎么办呢？

改进方法已经在代码里了，就是在进行下一次dfs的时候我们只需要写上i就行，而不是i+1,如果是i+1就会严格单调了。

只是这样写起来，会有数据点TLE。这是为什么呢？因为有些地方是需要剪枝的。那么这里我们怎么剪枝呢？如果你想说在求出来的和不是n的时候剪枝，那也是在全部数字枚举出来的时候才会判断的，仅仅是这样并不能完全剪枝。那该怎么办呢？这里，我们直接在循环里剪枝，也就是在枚举的过程中进行剪枝。怎么剪枝呢？举个例子：

当我们n=7，k=4时，这个时候假如我们已经列举到1，3了，现在正在第三个位置的dfs当中，这个时候按照我们的写法下一个数字肯定是3，最后一个数字也是3，这是对于自己编写的程序的理解。

我们看，如果这几个数字加起来是不是已经超过7了？也就是说，第四个位置我们根本不需要考虑了，前面已经=7了，后面再加就不行了，这里我们直接让循环不去dfs了，而是进行下一次循环。这就省了一次dfs函数的调用！那么，怎么实现这种想法呢？

我们在循环中改进循环条件就行，这和上几次的剪枝是不一样的，这里的剪枝涉及到的是对于在枚举过程中的剪枝，而不是对于全部枚举完之后的剪枝，这里是不同点。在上面的例子中，我们看到，其实知道了第三个数字我们也就知道了第四个数字了。所以，我们只需要循环到第二个位置后，判断后面两个位置的和与前面我们已经计算了的sum相加是不是<=n就行了，这就是优化的地方。

注意：这里的dfs有三个变量，第一个是位置，第二个是从哪个数开始枚举，第三个则是累加的数用来记录的。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 100010
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int arr[MAX];
LL n, m, counts, num;
void dfs(int  u,int st,int sum) {if (u > m) {if (sum<n || sum>n)return;else {counts++;}return;}for (int i = st; sum+(m-u+1)*i <= n; i++) {arr[u] = i;dfs(u + 1,i,sum+i);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;
}