一、 问题 现在有一正整数N，要把它分为若干正整数之和，问有多少种本质不同的分法？

（1）其中最大数不超过m, 有多少种分法？

（2）分割后的正整数的数目不超过m个， 有多少种分法？

（3）分成最大数不超过m， 且每一个正整数都是正奇数， 有多少种分法？

（4）分成最大数不超过m， 且每一个正整数都不同，有多少种分法？

（5）分成恰好k个正整数，有多少种分法？

二、分析

（1）最大数不超过 m

　　（a）设dp[i][j]表示把数字 i 分成最大数不超过  j 的若干正整数之和所得的方法数

　　（b）有如下递推公式 ，核心是最大数m到底选还是不选

（2）分割数不超过m个

　　（a）设dp[i][j] 表示把数字 i 分成分割数不超过 j 的若干正整数之和所得的方法数

　　（b）递推公式核心：

  • 到底分不分成 j 个

    • 　　如果分成j个，则预先给每一份分 一个1，那么还剩下n-m，这n-m仍然继续分割成最多j个数；
    • 　　如果不分成j个，那就转移到了把 i 最多分成 j-1 个数的状态
  • 递推公式：

  • 发现竟然和（1）完全一样！其实（1）（2）问题是完全等价的

    • 　　从递推公式上来看，等价
    • 　　从图形来看等价：

（3）分成最大数不超过m， 且每一个数都是正奇数

　　（a）设dp[i][j] 表示把数字 i 分成分割数不超过 j 的若干正奇数之和所得的方法数

　　（b）递推公式核心： 最大数 j 到底是不是奇数

  • 如果是奇数，那么 j 是可以作为 一种分法的元素的 转态转移到到底是分出 j 还是不分出 j
  • 如果不是奇数， 那么 j 是不能分出来的，状态转移到了dp[i][j-1]

（4）分成最大数不超过m， 且每一个正整数都不同

　　（a）设dp[i][j] 表示把数字 i 分成最大数不超过 j 的若干不同正整数之和所得的方法数

　　（b）递推公式核心：当前最大数选还是不选，如果选，还剩下i-j并且下次的最大数不能再是j而是j-1， 如果不选，状态转移到dp[i][j-1]

（5）分成恰好k个正整数

　　（a）设dp[i][j] 表示把数字 i 分成 j 个正整数之和所得的方法数

　　（b）递推公式核心：

  • 这j个数里面含不含有1

    • 　　若不含1，则先为每份预分配一个1，再对i-j进行分割成j份；
    • 　　若含1，则先分出一个1， 然后再对剩下的的i-1分成 j-1份

【记忆化搜索代码】

#include<iostream>

#include<queue>

#include<list>

#include<vector>

#include<cstring>

#include<set>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cmath>

#include<algorithm>

#include<string>

#include<stdio.h>

using namespace std;

typedef long long ll;

const double eps=1e-;

const double PI = acos(-1.0);

const int inf = 0x3f3f3f3f;

const ll INF = 0x7fffffff;

#define MS(x,i) memset(x,i,sizeof(x))

#define rep(i,s,e) for(int i=s; i<=e; i++)

#define sc(a) scanf("%d",&a)

#define scl(a) scanf("%lld",&a)

#define sc2(a,b) scanf("%d %d", &a, &b)

#define dubug printf("debug......\n");

const int maxn = 1e2+;

int dx[] = {, , , -};

int dy[]  = {, -,  , };

/*

1. 把n划分成若干正整数之和 最大数不超过m 方法数

2. 把n划分成不超过m个正整数之和 方法数

1.2 等价

*/

ll dp1[maxn][maxn];

ll dp2[maxn][maxn];

ll dp3[maxn][maxn];

ll dp4[maxn][maxn];

//把n划分成不超过m的若干正整数之和     把n划分成不超过m个正整数之和 方法数

ll DP1(int n, int m){

    if(dp1[n][m] != -){

        return dp1[n][m];

    }

    ll ans = ;

    if(m ==  || n == ){

        return dp1[n][m] = ;

    }

    if(m == n){

        return dp1[n][m] = DP1(n , m - ) + ;

    }

    if(m > n){

        return dp1[n][m] = DP1(n,n);

    }

    if(m < n){

        return dp1[n][m] = DP1(n-m, m) + DP1(n , m-);

    }

    return dp1[n][m] = ;

}

//把N分成不超过m的，若干个正奇数的和 的方法数

ll DP2(int n , int m){

    if(dp2[n][m] != -) return dp2[n][m];

    if(n ==  || m == ){

        return dp2[n][m] = ;

    }

    if(n == m){

        return dp2[n][m] = DP2(n , m-) + m%;

    }

    if(n < m){

        return dp2[n][m] = DP2(n , n);

    }

    if(n > m){

        if(m % ){

            return dp2[n][m] = DP2(n-m , m) + DP2(n , m-);

        }

        else{

            return dp2[n][m] = DP2(n , m - );

        }

    }

    return dp2[n][m] = ;

}

//把N划分成不超过m的 不同正整数之和 的方法数

ll DP3(int n, int m){

    if(dp3[n][m] != -){

        return dp3[n][m];

    }

    if(n == ) return dp3[n][m] = ;

    if(m ==  && n > ){

        return dp3[n][m] = ;

    }

    if(m == n){

        return dp3[n][m] = DP3(n , m - ) + ;

    }

    if(m > n){

        return dp3[n][m] = DP3(n,n);

    }

    if(m < n){

        return dp3[n][m] = DP3(n-m, m-) + DP3(n , m-);

    }

    return dp3[n][m] = ;

}

//把n换分成恰好k个正整数之和

ll DP4(int n, int k){

    if(dp4[n][k] != -) return dp4[n][k];

    if(n ==  && k > ) return dp4[n][k] = ;

    if(k == ) return dp4[n][k] = ;

    if(n == k) return dp4[n][k] = ;

    if(n < k) return dp4[n][k] = ;

    if(n > k) return dp4[n][k] = DP4(n-k , k) + DP4(n-, k-);

    return ;

}

int n,m;

int k;

int main(){

    while(sc(n) != EOF){

        MS(dp1, -);

        MS(dp2 , -);

        MS(dp3 , -);

        MS(dp4 , -);

        sc(k);

        //printf("%lld\n", DP1(n,n));

        printf("%lld\n", DP4(n,k));

       // printf("%lld\n", DP1(n,k));

        printf("%lld\n", DP3(n,n));

         printf("%lld\n", DP2(n,n));

    }

    return ;

}

【DP代码】

#include<iostream>

#include<queue>

#include<list>

#include<vector>

#include<cstring>

#include<set>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cmath>

#include<algorithm>

#include<string>

#include<stdio.h>

using namespace std;

typedef long long ll;

const double eps=1e-;

const double PI = acos(-1.0);

const int inf = 0x3f3f3f3f;

const ll INF = 0x7fffffff;

#define MS(x,i) memset(x,i,sizeof(x))

#define rep(i,s,e) for(int i=s; i<=e; i++)

#define sc(a) scanf("%d",&a)

#define scl(a) scanf("%lld",&a)

#define sc2(a,b) scanf("%d %d", &a, &b)

#define dubug printf("debug......\n");

const int maxn = 1e2+;

int dx[] = {, , , -};

int dy[]  = {, -,  , };

int n;

int k;

ll dp1[maxn][maxn];//把n划分成若干正整数之和且最大数不超过m    方法数   或者   把n划分成不超过m个正整数之和 方法数

ll dp2[maxn][maxn];//把N分成不超过m的，若干个【正奇数】的和 的方法数

ll dp3[maxn][maxn];//把N划分成不超过m的 【不同】正整数之和的方法数

ll dp4[maxn][maxn];//把n换分成【恰好k个】正整数之和

//把n划分成若干正整数之和且最大数【不超过m】    方法数   或者   把n划分成不超过【m个】正整数之和 方法数

void DP1(){

    MS(dp1, );

    rep(i,,n){

        rep(j,,n){

            if(i ==  || j ==  ){

                dp1[i][j] = ;

                continue;

            }

            if(j < i)

                dp1[i][j] = dp1[i-j][j] + dp1[i][j-];

            else if(j > i)

                dp1[i][j] = dp1[i][i];

            else

                dp1[i][j] = dp1[i][j-] + ;

        }

    }

}

//把N分成不超过m的，若干个【正奇数】的和 的方法数

void DP2(){

    MS(dp2, );

    rep(i,,n){

        rep(j,,n){

            if(i ==  || j == ){

                dp2[i][j] = ;

                continue;

            }

            if(j < i){

                if(j % )

                    dp2[i][j] = dp2[i-j][j] + dp2[i][j-];

                else{

                    dp2[i][j] = dp2[i][j-];

                }

            }

            else if(j == i){

                dp2[i][j] = j% + dp2[i][j-];

            }

            else

                dp2[i][j] = dp2[i][i];

        }

    }

}

//把N划分成不超过m的 【不同】正整数之和的方法数

void DP3(){

    MS(dp3, );

    rep(i,,n){

        rep(j,,n){

            if(i ==  ){

                dp3[i][j] = ;

                continue;

            }

            if(j ==  && i > ){

                dp3[i][j] = ;

                continue;

            }

            if(i < j) dp3[i][j] = dp3[i][i];

            if(i == j ){

                dp3[i][j] =  + dp3[i][j-];

            }

            if(i > j){

                dp3[i][j] = dp3[i-j][j-] + dp3[i][j-];

            }

        }

    }

   // cout<<dp3[5][5]<<endl;

}

//把n换分成【恰好k个】正整数之和

void DP4(){

    MS(dp4 , );

    rep(i, , n) {

        rep(j , , n){

            // if(i == 1 && j > 1) {

            //     dp4[i][j] = 0;

            //     continue;

            // }

            if(j == ) {

                dp4[i][j] = ;

                continue;

            }

            if(i == j) dp4[i][j] = ;

            if(i > j)

                dp4[i][j] = dp4[i-j][j] + dp4[i-][j-];

            if(i < j)

                dp4[i][j] = ;

        }

    }

}

int main(){

    while(sc(n) != EOF){

        sc(k);

        DP1();

        DP2();

        DP3();

        DP4();

        cout<<dp4[n][k]<<endl;

        cout<<dp3[n][n]<<endl;

        cout<<dp2[n][n]<<endl;

    }

    return ;

}

最新文章

  1. 常用命令[Linux]
  2. OracleConnection is obsolete
  3. lumen 错误&amp;日志
  4. Strict Standards: Only variables should be passed by reference
  5. 解决phpcms图片太大撑破表格图片自适应图片按比例缩小
  6. h.264码流解析_一个SPS的nalu及获取视频的分辨率
  7. iOS开发-自动布局篇：史上最牛的自动布局教学！
  8. shell脚本实现检測回文字符串
  9. left join 关联条件位置
  10. wlan0 Interface doesn&#39;t support scanning : Device or resource busy
  11. 3D转换
  12. 君子性非异也，善假于物也 - Threejs 引入TrackballControls 查看场景
  13. shell(sed/gawk)脚本（计算目录文件/验证电话号码/解析电子邮件地址）
  14. Activiti6-TaskService（学习笔记）重要
  15. Android OpenSL ES 开发：Android OpenSL 介绍和开发流程说明
  16. 线段树合并+并查集 || BZOJ 2733: [HNOI2012]永无乡 || Luogu P3224 [HNOI2012]永无乡
  17. 集合 （set）
  18. 『TensorFlow』第七弹_保存&amp;载入会话_霸王回马
  19. PHP中VC6、VC9、TS、NTS版本区别与用法
  20. JS 数组 foreach 和 map

热门文章

  1. Oracle 遇到的问题：IMP-00041: 警告: 创建的对象带有编译警告解决办法
  2. OZ常见错误解决办法
  3. 【Linux】wc ：字数统计命令
  4. 立体匹配之Census Transform
  5. Linux开启MySQL远程连接
  6. poj 1035 纯正的字符串水
  7. 【Nescaf&#233; 31】杯NOIP模拟赛
  8. [codeforces934D]A Determined Cleanup
  9. THUWC2018 题解
  10. [ARC068F] Solitaire [DP]