专栏首页ACM算法日常勇士与公主(组合+完全背包)- HDU 1028

勇士与公主(组合+完全背包)- HDU 1028

这是一道排列组合题,然而却用到了完全背包的思想,寻找真相并不是件容易的事情,先简单看下题目,慢慢进入正题

Problem Description

"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says. "The second problem is, given an positive integer N, we define an equation like this: N=a[1]+a[2]+a[3]+...+a[m]; a[i]>0,1<=m<=N; My question is how many different equations you can find for a given N. For example, assume N is 4, we can find: 4 = 4; 4 = 3 + 1; 4 = 2 + 2; 4 = 2 + 1 + 1; 4 = 1 + 1 + 1 + 1; so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"

看不懂英文可以直接看上面对数字4的拆解,简单的说就是对任意的数N,计算出有多少中拆解组合,注意4=3+1和4=1+3是一个组合。

Input

The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

输入N。

Output

For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

输出拆解组合的数量P。

Sample Input

4
10
20

Sample Output

5
42
627

请先烧脑1分钟。

......

解题思路:

1、这个题的题意简单,解法关键只有三行代码,然而要理解起来却非常困难,好吧,难道是我数学天分太差

2、在做题之前,我们可能想到用函数f(x)与f(x-1)之间的关系,可是很难建立这样的状态转移方程。

3、分解一下,采用背包的思想,求f(x),比如f(4),那么装背包时最大先用4来装,最大再用3,最大再用2...,最大用1。

4、这样可以建立一个方程,设 F(x, n)表示对于x,采用小于等于n的数字来拆解,有多少种解法

5、那么就有 f(x) = F(x, x),如f(6) = F(6, 6),表示用小于等于6的数字来拆解的解法数。

6、先看一个具体的例子,F(6, 1) 表示6全部用1拆解,F(6, 2)表示用1、2拆解,那么F(6, 2) = F(6, 1) + F(4, 2),如果你能理解这一步,就能理解状态转移方程:

F(x, n) = F(x, n-1) + F(x - n, n)

再来看F(6, 2) = F(6, 1) + F(4, 2)是为什么呢?

这里6先用1来拆,那么只剩下用2来拆的情况,用2拆的时候,因为已经固定了拆掉1个2,那么还剩下4要用小于等于2的数来拆。

这样理解起来再看代码就能很快明白这几行代码的作用了。

处理的时候需要先后处理F(1,1), F(2,1)...F(6,1), F(2,2),...F(6,2),...,F(6,6)。

如下图是整个过程:

源代码:G++ 0ms

#include<stdio.h>
#include<string.h>

int main()
{
    int dp[200];
    int n;

    while (~scanf("%d", &n)) {
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++) {
                //这里其实暗含一个方程式,这是理解该解法的关键
                //F(j,i) = F(j, i-1) + F(j-i, i) 
                dp[j] += dp[j - i];
            }

        printf("%d\n", dp[n]);
    }

    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DP专题 | LIS POJ - 2533

    A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence o...

    ACM算法日常
  • DP专题 5 | 颜色的长度 - UVA1625(线性DP)

    题目链接 https://cn.vjudge.net/problem/UVA-1625

    ACM算法日常
  • 牛客国庆集训派对Day6 E-Growth(离散化DP)

    链接:https://ac.nowcoder.com/acm/contest/206/E

    ACM算法日常
  • HDUOJ----Ignatius and the Princess III

    Ignatius and the Princess III Time Limit: 2000/1000 MS (Java/Others)    Memory L...

    Gxjun
  • 在NVIDIA Jetson TX2上编译背景建模库(BGSLibrary)

    BGSLibrary,A Background Subtraction Library,包含了几十种背景建模算法,可以显示输入视频/图像、基于背景建模得到的前景...

    GPUS Lady
  • Dropbox推Office协同工具

    4月10日消息,据国外媒体报道,云服务商Dropbox周三发布一系列新移动应用,并推出能增进与微软Office软件协同工作的Project Harmony工具。...

    静一
  • MySQL5.6.21安装版出现the the service mysql56 failed问题的方法。

    http://blog.csdn.net/u014677820/article/details/44996905

    bear_fish
  • C++核心准则E.6:使用RAII防止资源泄露

    Leaks are typically unacceptable. Manual resource release is error-prone. RAII (...

    面向对象思考
  • HDUOJ------Daydream字符查找-并求其始末位置

    2013-07-17  10:50:38 Daydream Time Limit: 2000/1000 MS (Java/Others)    Memory L...

    Gxjun
  • SAP UI5 Diagnostics工具里一个使用面向切片编程(AOP)的一个例子

    We know that UI5 framework provides a convenient Diagnostics tool for applicatio...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券