信息学奥赛一本通T1440:深搜的剪枝技巧 数的划分

【题目描述】将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。1,1,5; 1,5,1; 5,1,1;问有多少种不同的分法。 输出一个整数,即不同的分法【输入】两个整数n,k(6<n≤200,2≤k≤6),中间用单个空格隔开。【输出】一个整数,即不同的分法。【输入样例】7 3【输出样例】4【源程序】 

信息学奥赛一本通T1440:数的划分

【题目描述】

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。

例如:n=7,k=3,下面三种分法被认为是相同的。

1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。 输出一个整数,即不同的分法

【输入】

两个整数n,k(6<n≤200,2≤k≤6),中间用单个空格隔开。

【输出】

一个整数,即不同的分法。

【输入样例】

7 3

【输出样例】

4

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int res;
int a[N];
int n,k;
void dfs(int sum,int step){
    if(step==k){
        if(sum>=a[step-1])
            res++;
        return;
    }

    for(int i=a[step-1];i<=sum/(k-step+1);i++){//上下界剪枝
        a[step]=i;
        sum-=i;
        dfs(sum,step+1);
        sum+=i;
    }
}
int main() {
    scanf("%d%d",&n,&k);
    a[0]=1;
    dfs(n,1);
    printf("%d\n",res);
    return 0;
}

 

信息学奥赛一本通T1440:深搜的剪枝技巧 数的划分 归属于 深搜的剪枝技巧,更多同类题解源程序见:深搜的剪枝技巧 和 数的划分

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章