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

 

做呢题……我领略到思考层层推进果种魅力，同埋果种快感{=__, =}

呢题其实就系组合数学里面既自然数拆分吧，而且最大都只不过系120，所以我首先念到DFS：

 

DFS(int x, int bx);

 

x为剩余大小，bx为拆分既上一个数字，例如： 4 = 3 + 1   递归到DFS(1, 3) 当前剩余大小为1，上一个拆分数为3，

bx可以保证拆分无重复，可以参考题目，但系发觉50+就已经超时鸟{=   =}

跟住呢个时候我捻到用一维数组做记忆化DFS：

 

int dp[MAXI];

 

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

所以我就直接加入判断：

 

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

 

但系呢个时候有个问题就系，拆分既前一个数bx必须不小于x，先正可以直接返回dp[x]，所以我又加入判断：

 

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

 

但系，都中系超时窝，跟住我就捻到一个例子：10 = 1 + .... 即系当x > bx既时候，会一直递归落去，例如120既全1拆分

就会递归120层，呢种情况我无优化到，所以超时鸟。

跟住我捻到可吾可以构造一个二维数组：

 

int dp[i][j];

 

呢个数组记录既系数i第一个拆分数为j既时候拆分方法有几种，点解会甘捻？其实原因真系好简单，因为我地宜家要解决

既问题系x > bx即剩余大小大于前一个拆分数既情况，举个例子：

 

10 = 2 + .......

 

其实姐系DFS(8, 2)既情况，因为呢个时候x > bx 所以会进入2~1既循环，继续递归，但系！其实问题可以转化为：

 

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

 

姐系10第一个拆分数为2既情况其实就系等于8第一个拆分数为2既情况，即dp[8][2]！！，所以如果我地知道dp[8][2]，就可以

直接加上而唔洗继续DFS(6, 2)，所以我就系循环果度加入判断：

 

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

tsu += dp[x][i];

 

不过呢个时候又出现一个问题，就系如果一开始就DFS(n, n)系无用既，因为dp并无记录n以下既数据，所以我地要做既就系从

1开始做DFS递推上去！

 

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

 

最后其实我地不必每次输入都做一次DP，其实初始化做一次，我地就已经保存左所有答案。

 

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

 

每次输入就直接输出dp[n][n]即可，即系俗称打表。

 

下面AC代码:

 

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

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