题解 2352: 信息学奥赛一本通T1440-数的划分

解题思路:整体思想是通过dfs去找符合n划分次数为k有多少种情况

参考代码:

#include <bits/stdc++.h>//万能头
using namespace std;
int n,k,ans;
void dfs(int he,int cnt,int sx){//表示和，次数，升序（因为划分的数是按升序排列的）
	if(cnt==k){//当次数为k时，判断和是否为n，是，划分次数加一
		if(he==n) ans++;
		return;
	}
	if(he>n) return ;//he超过直接返回
	for(int i=sx;he+i*(k-cnt)<=n;i++)//这里剪枝he+i*(k-cnt)的值不能超过n,避免数据的重复运算
	 dfs(he+i,cnt+1,i);//继续搜
}
int main()
{
	ios::sync_with_stdio(false);//这个可以将c++的cin,cout输出速度变得跟c里面的scanf和printf一样
	cin>>n>>k;//输入数和需要划分的个数
	if(n==0||k==0||n<k){//特殊判断一下不能分的情况
		cout<<0;
		return 0;
	}
	dfs(0,0,1);//深搜
	cout<<ans;
	return 0;
}

这种方法的运行速度不是很好，下面使用回溯的方法，能更快速度的解决这个问题

#include<bits/stdc++.h>

using namespace std;

int n,m,a[8],s;
void dfs(int k){
    if(n==0) return;
    if(k==m){
        if(n>=a[k-1]) s++;//计数
        return;
    }
    for(int i=a[k-1];i<=n/(m-k+1);i++){//剪枝
        a[k]=i;//选择i作为a[k]的值
        n-=i;
        dfs(k+1);
        n+=i;//回溯；
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    a[0]=1;
    dfs(1);//从1开始划分
    cout<<s<<endl;
    return 0;
}