# HDU 1028 Ignatius and the Princess III

www.MyException.Cn  网友分享于：2013-11-20  浏览：6次
HDU 1028 Ignatius and the Princess III .

# Ignatius and the Princess III

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4658    Accepted Submission(s): 3263

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`

Author
Ignatius.L

DFS(int x, int bx);

x为剩余大小，bx为拆分既上一个数字，例如： 4 = 3 + 1   递归到DFS(1, 3) 当前剩余大小为1，上一个拆分数为3，
bx可以保证拆分无重复，可以参考题目，但系发觉50+就已经超时鸟{=   =}

int dp[MAXI];

dp[x]表示数字x既拆分方法有几种，甘样当递归到DFS(int x, int bx)时如果dp[x] > 0就可以直接返回dp[x]。

if (dp[x]) return dp[x];

if (dp[x] && dp[x] <= bx) return dp[x];

int dp[i][j];

10 = 2 + .......

10 = 2 + {8 = 2 + .......}

if (!dp[x][i]) dp[x][i] = DFS(x - i, i);
tsu += dp[x][i];

1开始做DFS递推上去！

for (i = 0; i <= n; i++) dp[i][i] = DFS(i, i);

for (i = 0; i <= 120; i++) dp[i][i] = DFS(i, i);

 4277486 2011-07-28 13:31:08 Accepted 1028 0MS 296K 595 B C++ 10SGetEternal{（。）（。）}!
```#include <iostream>
#include <vector>
using namespace std;
#define MAXI 122

int dp[MAXI][MAXI], n;

int DFS(int x, int bx)
{
int i;
int tsu = 0;

if (dp[x][x] && x <= bx) return dp[x][x];
for (i = bx; i >= 1; i--)
{
if (!dp[x][x - i])
dp[x][x - i] = DFS(x - i, i);
tsu += dp[x][x - i];
}

return tsu;
}

int main()
{
int i, j;

for (i = 0; i <= MAXI; i++)
for (j = 0; j <= MAXI; j++ )
dp[i][j] = 0;
for (dp[0][0] = i = 1; i <= MAXI; i++)
dp[i][i] = DFS(i, i);
while (scanf("%d", &n) != EOF) printf("%d\n", dp[n][n]);

return 0;
}```

当然我呢种捻法比较复杂，其实自然数拆分可以直接计算，不过我想讲既系思考既层层递进，真会系好爽