#计蒜客:整数划分//背包问题--wizard

#计蒜客:整数划分//背包问题

#计蒜客:整数划分//背包问题--wizard

我们今天来一个五连鞭


大家好,我是wizard,我们普遍知道,背包问题是我们普遍利用的问题,下面我根据背包问题作以下问题的题解:
#计蒜客:整数划分//背包问题--wizard

一鞭:原题

整数划分问题是算法中的一个经典命题之一。把一个正整数n表示成一系列正整数之和:
正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数,记作P(n) 。
正整数6有如下11种不同的划分,所以P(6)=11。
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1

二鞭:计蒜客:传送门

https://www.jisuanke.com/course/11568/686896

所谓整数划分,是指把一个正整数n写成如下形式:

n=m1+m2+…+mi; (其中mi为正整数,并且1 <= mi <= n),则:{m1,m2,…,mi}为n的一个划分。

如果{m1,m2,…,mi}中的最大值不超过m,即max(m1,m2,…,mi)≤m,则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);

例如:当n=4时,共有5个划分,{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

注意4=1+3 和 4=3+1被认为是同一个划分。

该问题是求出n的所有划分个数,即f(n, n)。

通用的递推公式如下:
      f(n, m) = 1; ( n = 1 or m = 1 )

                          f(n, n);                                 ( n < m )

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

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

三鞭:AC代码

//我们知道,在计蒜客写代码都是要带文件输入输出的:

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+9;
const int MOD=1e9+9;
int f[N];
int main(){
    freopen("divide.in","r",stdin);
    freopen("divide.out","w",stdout);
    int T;
    cin >> T;
    while(T--){
        memset(f,0,sizeof (f));
        f[0]=1;
        int n;
        cin >> n;
        for(int i =1;i<=n;i++){
            for(int j=i;j<=n;j++){
                f[j]=(f[j]+f[j-i])%MOD;
            }
        }
        cout << f[n] << endl; 
    }
    return 0;
}

四鞭: 非常好用

五鞭:防抄标记

//原创.wizard
Tel:18829879339
QQ:3168950143
wechat:fjb20080607
bye~~!

上一篇:如何修改CodeBlocks创建项目默认的main.cpp


下一篇:用ystep去实现一个月份时间轴