【洛谷p1025】数的划分

算法的话，dfs+剪枝；

据说是01年之前的NOIp提高组；

思路：

这道题是求把n无序的划分成k份的方案数，最直接的搜索方法是依次枚举x₁，x₂……x_k的值，然后判断，显然这么搜索的话，很容易就TLE了qwq。所以我们需要剪枝，这道题用到的主要是可行性剪枝和上下界剪枝；

①因为本题不考虑分解的顺序，所以我们可以规定分成的这k个数是从小到大分的，即a[i]<=a[i+1]。

②假设我们已经把n分解为i-1个数分别为a[1],a[2]……a[i-1]（其中a[1]<=a[2]<=……<=a[i-1]），那么a[i]的最大值是将剩余k-i+1个数平均划分，即设m=n-（a[1]+a[2]+……+a[i-1]），那么a[i]<=m/(k-i+1)，所以对于每个a[i]，扩展上届为m/(k-i+1)；

经过剪枝，好像就快一点了qwq；

#include<bits/stdc++.h>

using namespace std;

int n,m,a[],s;

void dfs(int k){

    if(n==) return;

    if(k==m){

        if(n>=a[k-]) s++;//计数

        return;

    }

    for(int i=a[k-];i<=n/(m-k+);i++){//剪枝

        a[k]=i;//选择i作为a[k]的值

        n-=i;

        dfs(k+);

        n+=i;//回溯；

    }

}

int main(){

    cin>>n>>m;

    a[]=;

    dfs();//从1开始划分

    cout<<s<<endl;

    return ;

}

巴特西

【洛谷p1025】数的划分

最新文章

热门文章