洛谷 P1205数的划分

迈不过友情╰ 2022-07-15 11:17 232阅读 0赞

**P1025 数的划分**  
题目描述  
将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。  
例如：n=7，k=3，下面三种分法被认为是相同的。  
1，1，5; 1，5，1; 5，1，1;  
问有多少种不同的分法。  
输入格式：n，k (6

var total,n,k,now:longint;
     procedure dfs(t,now,back:longint);
      var i:longint;
      begin
       if t=1 then
        begin
          if now>=back then inc(total);
        end
       else
        for i:=back to  now div t do
          dfs(t-1,now-i,i);
      end;
    begin
     readln(n,k);total:=0;now:=0;
     dfs(k,n,1);
     write(total);
    end.

**别人代码**

一个简单的DP思路。

题目要求k个盒子里必须都有球，那么就先在所有的盒子里都放一颗球，于是还剩下n-k颗。这n-k颗可以都放在一个盒子里，也可以放在两个盒子里，也可以放在三个盒子里……最多可以放在min(n-k,k)个盒子里，于是得到递推式dp\[i,j\]:=∑dp\[i-j,i1\] (i1∈(1,min(i-j,k)));

代码如下

Var
        dp:array[0..210,0..210] of longint;
        n,k,i,j,i1,j1:longint;
    Function min(a,b:longint):longint;
        begin if a<b then exit(a);
            exit(b);
        end;
    Begin readln(n,k);
        fillchar(dp,sizeof(dp),0);
        for i:=0 to n do begin dp[i,i]:=1;
            dp[i,1]:=1;
        end;
        for i:=3 to n do for j:=2 to min(i-1,k) do for i1:=1 to min(j,k) do begin //writeln('dp[',i,',',j,']+=dp[',i-j,',',i1,']=',dp[i-j,i1]);
                    dp[i,j]:=dp[i,j]+dp[i-j,i1];
                end;
        writeln(dp[n,k]);
    End.

设n个物体分成m份则以下函数关系:

f(n,m)=0 m>n; f(n,m)=1 m=1; f(n,m)=0 m=0; f(n,m)=f(n-1,m-1)+f(n-m,m);

以下代码

#include <stdio.h>
    #include <iostream>
    using namespace std;
    int n,m;
    int div(int n,int m){
      if(m>n) return 0;
      if(m==1) return 1;
      if(n==0) return 0;
      return div(n-m,m)+div(n-1,m-1);
    }
    int main(){
        cin>>n>>m;
        cout<<div(n,m);
     return 0;
    }