题解：P1025 [NOIP2001 提高组] 数的划分

别人内卷我在躺平 · 2025-01-27 15:49:47 · 题解

本题算法：搜索。
这题就是分苹果，一模一样。注意到题目有一句话：“每份不能为空，任意两个方案不相同。”那么，什么是相同呢？就是说 2,2,3 和 3,2,2 是重复的，那么，我们可以让分配方案中的每一份都递增。我们用 ans 数组存储答案，每次从 ans_{x-1} 开始枚举到 n-sum。这里的 sum 就是剩下的数的和，因为如果和超过了 n 那么这个方案就不成立了。在循环时，如果这个数没有用过，就存进答案，看下一个数，否则退回来，把标记也变成 0，和减去 i。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int n,k;
int ans[maxn];
int sum=0;
int total=0;
void dfs(int x)
{
    if(x>k)
    {
        if(sum==n) total++;
        return ;
    }
    for(int i=ans[x-1];i<=n-sum;i++)
    {
        if(i==0) continue;
        ans[x]=i;
        sum+=i;
        dfs(x+1);

        ans[x]=0;
        sum-=i;
    }
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    dfs(1);
    cout<<total; 
    return 0;
}