【NOIP2001】【Luogu1025】数的划分(可行性剪枝,上下界剪枝)

            

problem

  • 将整数n分成k份,
  • 满足1、每份不能为空
  • 满足2、任意两种划分方案不能相同(不考虑顺序)
  • 问有多少种不同的分法
  • n<=200,k<=6

例:n=7,k=3:1,1,5;,,,,,1,5,1;,,,,5,1,1是一样的。

solution

1、答案

  • 无序划分n个数为k份且不重复,等价于求方程(x1+x2+x3+…xk=n且1<=x1<=x2<=…xk)的解的个数。(x为每份的值)
  • 搜索的方法是依次枚举x1,x2,x3…xk。复杂度O(n^k),直接上天。

2、剪枝

  • 可行性剪枝(分支无法到达递归边界,远远的看到前方是死胡同,得不到答案):未到第k份n就被分完了,n<=0时,return;
  • 上下界剪枝(也是可行性的一种,限制范围是区间):考虑约束条件
    1、下界:由于分解不考虑顺序,我们设分解数依次递增,所以拓展节点时的下界应该不小于前一个节点的值,即a[i-1]<=a[i]。(这样还可以避免重复,直接起到判重的作用)【就是大于前一个数】
    2、上界:假设我们已经将n分成了a[1]+a[2]+…a[i-1]份,则a[i]的最大值为i-k这k-i+1份的平均划分(因为后面都>=a[i]啊,最好的结果就是都等于)。即设剩余数大小为m=n-(a[1]+a[2]+..a[i-1]),就有a[i]<=m/(k-i+1)。 【其实就是剩余数总大小除以剩余的份数,平均值就是最大值。】

复杂度能AC。

codes

#include
using namespace std;
int n, m, a[8], sum;
void dfs(int k){//分第k份
    if(n == 0)return ;//可行性剪枝,分不到n份了
    if(k == m){
        if(n >= a[k-1])sum++;//严格递增,不然判重炸锅
        return ;
    }
    for(int i = a[k-1]; i <= n/(m-k+1); i++){//上下界
        a[k] = i; //第k份的值
        n -= i;//不用全局也可以加参数
        dfs(k+1);
        n += i;
    }
}
int main(){
    cin>>n>>m;
    a[0] = 1;//每份不能为空:第一份(最小的)要>=1
    dfs(1);
    cout<'\n';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像