划分数白书

系统管理员 2023-07-12 05:05 11阅读 0赞

1 #include <iostream>
     2 #include <cstdio>
     3 
     4 using namespace std;
     5 // 有关计数问题的dp
     6 // 有n个无区别的物品，划分成不超过m组，求方法数取模M的余数
     7 
     8 const int max_n=1000+2;
     9 const int max_m=1000+2;
    10 const int max_M=10000+2;
    11 
    12 int n,m,M;
    13 int dp[max_M][max_M];
    14 
    15 // 定义dp[i][j]
    16 // 考虑dp[i][j-i],将dp[i][j-i]中所有划分（包括省略的0）+1,即得到新的满足要求的划分，且每一个划分最少是1
    17 // 另外，考虑可能有空划分的情况，这种情况，在dp[i-1][j]中已全部包含（考虑到递推定义过程）
    18 
    19 void solve()
    20 {
    21     dp[0][0]=1;
    22     for(int i=1;i<=m;++i)
    23     {
    24         for(int j=0;j<=n;++j)
    25         {
    26             if(j-i>=0)
    27             {
    28                 dp[i][j]=(dp[i-1][j] + dp[i][j-i]);
    29             }
    30             else
    31             {
    32                 dp[i][j]=dp[i-1][j];
    33             }
    34             // printf("%d ",dp[i][j]);
    35         }
    36         // printf("\n");
    37     }
    38 
    39     printf("%d\n",dp[m][n]);
    40 }
    41 
    42 int main()
    43 {
    44     scanf("%d %d %d",&n,&m,&M);
    45     solve();
    46     return 0;
    47 }
    48 /* test
    49 4 3 10000
    50 
    51 ans=4(1+1+2=1+3=2+2=4)
    52 */

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关划分数白书

1 include <iostream> 2 include <cstdio> 3 4 using namespace std;

系统管理员/ 2023年07月12日 05:05/ 0 赞/ 12 阅读

相关 P1025-数的划分

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

快来打我*/ 2023年06月01日 08:49/ 0 赞/ 8 阅读

相关小白学JAVA的话推荐什么书_零基础小白学java看什么书好

零基础学java看什么书，小白学java需要多久？四个月可以学好java吗，小白学java需要多久才能有所成就！在达内天津校区参加Java培训已经有两个多月了，我想对这段时

淡淡的烟草味﹌/ 2022年11月06日 05:47/ 0 赞/ 210 阅读

相关划分型动态规划——完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例 1: 输入:

水深无声/ 2022年10月27日 12:06/ 0 赞/ 115 阅读

相关集合划分问题（贝尔数）

集合划分问题 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submi

傷城~/ 2022年08月21日 11:56/ 0 赞/ 170 阅读

相关洛谷 P1205数的划分

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

谁借莪１个温暖的怀抱￠/ 2022年07月15日 11:17/ 0 赞/ 183 阅读

相关洛谷 P1205数的划分

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

迈不过友情╰/ 2022年07月15日 11:17/ 0 赞/ 234 阅读

相关算法训练数的划分

问题描述　　将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。　　例如：n=7，k=3，下面三种分法被认为是相同的。　　1，1，5; 1，5，1

╰+哭是因爲堅強的太久メ/ 2022年05月31日 05:51/ 0 赞/ 189 阅读

相关洛谷P1025 数的划分

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

迈不过友情╰/ 2022年05月29日 03:24/ 0 赞/ 218 阅读

相关 P1025-数的划分

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

痛定思痛。/ 2021年11月09日 07:42/ 0 赞/ 284 阅读