数的划分--dfs+剪枝

P1025 [NOIP 2001 提高组] 数的划分 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
int a[7];
int n,k;
ll an;
void dfs(int s,int c)
{if(c==k){if(s==0)///符合条件的 {an++;///直接+1就行，答案不会重复，因为是按递增写的 }else return;}if(c>k) return;///剪枝1 if(s<k-c) return;///剪枝2，说明后面不够1了 for(int i=max(a[c],1);i<=s;i++)///递增序，不重复还少dfs {a[c+1]=i;dfs(s-i,c+1);}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//solve();cin>>n>>k;dfs(n,0);cout<<an;return 0;
}