一道站外题，一直Wrong_answer

Question

这里

代码过不了一点，总是 Wrong_answer，怎么改代码过不了一点，总是 Wrong_answer，怎么写（C++代码）

注意时间限制和空间限制

HANOI07 - Building the Tower

题面翻译

题目描述

在一个玩具盒中有N个立方体，它有1个单位高度，宽度是高度的两倍。老师组织了一个塔楼游戏。这座塔是由立方体建造的。塔的高度为H（H水平）。塔的底部包含M立方体；对于所有以上的水平，每个都必须包含多个立方体，这些立方体正好小于或大于其正下方的立方体的数量。你的任务是确定那里有多少个不同的塔。如果至少有一个数字i（1＜i＝h），则两个塔被认为是不同的，因此一个塔的第i个水平包含不同数量的立方体到另一个塔的第i个水平。

输入格式：

输入文件的第一行是整数T（0＜T＜1002），T为测试用例的个数。在一行中的每个测试用例中，该行包含三个正数N、H和M（N<＝32767，H<=60，M<＝10）。

输出格式：

在每个测试用例中，用一条线写下可以建立的不同塔的总数。

输入输出样例

输入样例#1：

2
7 3 2
22 5 4

输出样例#1：

2
10

PS:在第一个测试样例中，所有的塔都是2-1-2，2-3-2。

感谢@silenceabu 提供的翻译

题目描述

There are N cubes in a toy box which has 1-unit height, the width is double the height. The teacher organizes a tower-building game. The tower is built by the cubes. The height of the tower is H (h levels). The bottom of the tower contains M cubes; and for all above level, each must contains a number of cubes which is exactly 1 less than or greater than the number of cubes of the level right below it. Your task is to determine how many different towers can be there. Two towers are considered different if there is at least one number i (1< i <=H) so that the i'th level of one tower contains a different number of cubes to the i'th level of the other tower.

输入格式

The first line of input file is the integer number t ( 0 < t < 1002 ) , the number of test cases . Each test case in one line , the line contains three positive number N, H and M (N <= 32767, H<=60, M<=10).

输出格式

With each test case , write in one line , the total of different towers that can be founded.

样例 #1

样例输入 #1

2
7 3 2
22 5 4

样例输出 #1

2
10
(* In the first test case , all the towers are : 2-1-2 , 2-3-2 . *)

时间限制
349ms
内存限制
1.46GB
C++代码

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

这个问题是一个组合数学问题，涉及到递归和动态规划。我们的目标是计算在给定条件下可以构建的不同塔楼的数量。

问题理解

• 塔楼的高度为 ( H ) 层。
• 塔楼底部（第 ( H ) 层）包含 ( M ) 个立方体。
• 每层的立方体数量必须比其正下方的层多或少一个。

算法思路

1. 递归关系：我们可以定义一个函数 ( f(n, h, m) ) 来表示在剩余 ( n ) 个立方体，构建高度为 ( h ) 的塔楼，且底部包含 ( m ) 个立方体的方法数。

2. 边界条件：当 ( h = 1 ) 时，如果 ( m \leq n )，则 ( f(n, 1, m) = 1 )，否则为 0。

3. 递归公式：对于 ( h > 1 )，我们可以将问题分解为两个子问题：

   • 构建一个高度为 ( h-1 ) 的塔楼，底部包含 ( m-1 ) 个立方体，剩余 ( n-m+1 ) 个立方体。
   • 构建一个高度为 ( h-1 ) 的塔楼，底部包含 ( m+1 ) 个立方体，剩余 ( n-m-1 ) 个立方体。

   因此，递归公式为： [ f(n, h, m) = f(n-m+1, h-1, m-1) + f(n-m-1, h-1, m+1) ]

动态规划优化

为了避免重复计算，我们可以使用动态规划来存储已经计算过的 ( f(n, h, m) ) 的值。

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 32768;
const int MAXH = 61;
const int MAXM = 11;

vector<vector<vector<long long>>> dp(MAXN + 1, vector<vector<long long>>(MAXH + 1, vector<long long>(MAXM + 1, 0)));

long long f(int n, int h, int m) {
    if (h == 1) {
        return (m <= n) ? 1 : 0;
    }
    if (dp[n][h][m] != 0) {
        return dp[n][h][m];
    }
    dp[n][h][m] = f(n - m + 1, h - 1, m - 1) + f(n - m - 1, h - 1, m + 1);
    return dp[n][h][m];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, H, M;
        cin >> N >> H >> M;
        cout << f(N, H, M) << endl;
    }
    return 0;
}

注意事项

• 确保初始化 dp 数组为 0，以避免未定义行为。
• 递归公式中的 ( n-m+1 ) 和 ( n-m-1 ) 需要确保不会超出立方体的总数 ( N )。
• 动态规划的维度需要根据题目给定的限制来设置。

时间和空间复杂度

• 时间复杂度：由于动态规划的使用，时间复杂度降低到 ( O(N \cdot H \cdot M) )。
• 空间复杂度：由于存储了所有的 ( f(n, h, m) ) 值，空间复杂度为 ( O(N \cdot H \cdot M) )。

这个算法应该能够在给定的时间和空间限制内解决问题。如果遇到性能问题，可以考虑进一步优化，例如通过剪枝或使用更高效的数据结构。