[GESP202509 七级] 金币收集

Question

题目描述
小 A 正在游玩收集金币的游戏。具体来说，在数轴上将会出现 n 枚金币，其中第 i 枚（1≤i≤n）金币将会在时刻 t
i
​
出现在数轴上坐标为 x
i
​
的位置。小 A 必须在时刻 t
i
​
恰好位于坐标 x
i
​
，才可以获得第 i 枚金币。

游戏开始时为时刻 0，此时小 A 的坐标为 0。正常来说，小 A 可以按游戏机的按键在数轴上左右移动，但不幸的是游戏机的左方向键失灵了。小 A 每个时刻只能选择保持不动，或是向右移动一个单位。换言之，如果小 A 在时刻 t 的坐标为 x，那么他在时刻 t+1 的坐标只能是 x 或是 x+1 二者之一，分别对应保持不动和向右移动。

小 A 想知道他最多能收集多少枚金币。你能帮他收集最多的金币吗？

输入格式
第一行，一个正整数 n，表示金币的数量。

接下来 n 行，每行两个正整数 x
i
​
,t
i
​
，分别表示金币出现的坐标与时刻。

输出格式
输出一行，一个整数，表示小 A 最多能收集的金币数量。

输入输出样例
输入 #1复制

3
1 6
3 7
2 4
输出 #1复制

2
输入 #2复制

4
1 1
2 2
1 3
2 4
输出 #2复制

3
说明/提示
对于 40% 的测试点，保证 1≤n≤8。

对于另外 30% 的测试点，保证 1≤n≤100，1≤x
i
​
≤100，1≤t
i
​
≤100。

对于所有测试点，保证 1≤n≤10
5
，1≤x
i
​
≤10
9
，1≤t
i
​
≤10
9
。

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题理解

根据你的问题描述，似乎是关于一个金币收集游戏的题目。小 A 需要在时刻 ti 出现的金币位置 xi 处收集金币。题目要求我们实现一个算法来解决这个问题。

问题关键点

• 金币的数量 n
• 每枚金币的出现时间 ti 和位置 xi
• 小 A 需要在每枚金币出现时收集它

解决方案

这个问题似乎是一个典型的动态规划问题。我们可以使用一个二维数组 dp 来存储每枚金币出现时的最大金币数量。

核心代码

int maxCoins(vector<int>& coins) {
    int n = coins.size();
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = i; k < j; k++) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins[k]);
            }
        }
    }
    
    return dp[0][n + 1];
}

注意

这个代码假设 coins 是一个从小到大的有序数组，表示每枚金币的数量。我们使用 dp[i][j] 来表示从 i 到 j 之间的最大金币数量。我们通过递归地选择每枚金币出现时的最大金币数量来计算 dp[i][j]。

时间复杂度

这个算法的时间复杂度是 O(n^3)，其中 n 是金币的数量。

空间复杂度

这个算法的空间复杂度是 O(n^2)，其中 n 是金币的数量。