# 勇士与公主（组合+完全背包）- 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!"

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.

Output

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

Sample Input

```4
10
20```

Sample Output

```5
42
627```

......

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)

```#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;
}```

0 条评论

• ### DP专题 | LIS POJ - 2533

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

• ### DP专题 5 | 颜色的长度 - UVA1625（线性DP）

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

• ### 牛客国庆集训派对Day6 E-Growth(离散化DP)

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

• ### HDUOJ----Ignatius and the Princess III

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

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

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

• ### Dropbox推Office协同工具

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

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

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

• ### 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...

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

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