数的划分-搜索-剪枝

题目

题目链接

分析

当时想到用搜索了，然后超时了，没想到好的剪枝。 样例7 3，也就是说从1到7中选三个数和为7，可以有重复的，比如 1 1 5，但是要注意 1 1 5，5 1 1，1 5 1，这种情况，只是一种。

#include<bits/stdc++.h> using namespace std; #define ll long long int n,k; int arr[201]; int b; void dfs(int st,int sum,int ans){//sum表示现在选择数的和，st表示循环找下一个数的 开始，保证后面的数大于等于前面的数，ans表示现在在找第几个数 if(sum==n&&ans==k+1){ //这个是满足条件的寻找 b++; return ; } if(ans>=k+1||st>=n||sum>n){ return ; } for(int i=st;i*(k-ans+1)<=n-sum;i++){ //i*(k-ans+1)<=n-sum 剪枝，太妙了，因为你找的数是越找越大的，如果现在还有（k-ans+1）个数没找， //用现在开始的最小值都大于剩余需要的值得话，就不用再进行循环了 dfs(i,sum+i,ans+1); //dfs(i,sum,ans); } } int main(){ for(int i=0;i<201;i++){ arr[i]=i; } cin>>n>>k; dfs(1,0,1); cout<<b<<endl; }