C++代码 Smart喜欢玩骨牌。一天,他沿着一条直线放了 n 颗骨牌,从左往右坐标依次为x1,x2,xn, 每颗骨牌都有它的高度,第i个骨牌的高度为hi Smart 可以放倒一颗骨牌,然后把它倒向左边,那它就占据了区间[xi-hi,xi]; 或者把它倒向右边, 那它就占据了区间[xi,xi+hi] ,没有被放倒的骨牌只占据一个坐标为xi的点。 现在的问题是他最多能放倒多少个骨牌,使得任意两个骨牌,彼此之间占据的部分都没有公共部分。
时间: 2023-05-30 19:03:43 浏览: 46
思路:贪心算法
首先我们需要明确一点,对于任意两个骨牌i和j,它们之间有公共部分的情况只有两种:
1. $x_i \leq x_j$,且$i$向右倒,$j$向左倒
2. $x_i \geq x_j$,且$i$向左倒,$j$向右倒
因此,我们可以考虑使用贪心算法,从左到右枚举每一个骨牌,对于每一个骨牌,我们可以考虑两种情况:
1. 不倒,直接跳过
2. 向左倒或向右倒,倒向哪一边取决于当前骨牌向左倒或向右倒能占据的范围更长
具体实现时,我们可以使用一个变量$last$来记录上一个被倒的骨牌的位置,如果当前骨牌不能倒,就跳过;否则,我们计算出向左倒和向右倒的范围,选取范围更长的方向倒下骨牌,同时更新$last$为当前骨牌的左右边界中更靠右的那个位置。
代码如下:
相关问题
有 2*n 的一个长方形方格,用一个 1 * 2 的骨牌铺满方格
题目描述:在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,输入n,输出铺放方案的总数。
解题思路:这是一道典型的动态规划问题。我们可以用f(n)表示铺满2×n方格的方案数。对于第一列,我们可以竖着放一块骨牌,这样就剩下2×(n-1)的方格需要铺满,方案数为f(n-1);或者横着放两块骨牌,这样就剩下2×(n-2)的方格需要铺满,方案数为f(n-2)。因此,f(n)=f(n-1)+f(n-2)。
代码实现:
多米诺骨牌游戏,有N个骨牌,把它们摆在一条直线上,已知它们的位置和高度,骨牌可以向左右两边倒,若它可以碰到附近的骨牌(若它倒下去,只能达到附近骨牌位置时,不算能打倒,即:这里的骨牌是没有厚度的)问:任意推倒一块骨牌,最多能打倒多少张骨牌!用Java实现
以下是Java实现代码:
```java
import java.util.Arrays;
public class DominoesGame {
public static int knockDown(int[] positions, int[] heights, int index) {
int n = positions.length;
int[] left = new int[n]; // left[i]表示从位置i往左最多能打倒的骨牌数
int[] right = new int[n]; // right[i]表示从位置i往右最多能打倒的骨牌数
// 初始化
Arrays.fill(left, 1);
Arrays.fill(right, 1);
// 计算left数组
for (int i = index - 1; i >= 0; i--) {
for (int j = i + 1; j <= index; j++) {
if (positions[j] > positions[i]) {
int diff = heights[j] - heights[i];
if (diff <= 0 || diff > positions[j] - positions[i]) {
left[i] = Math.max(left[i], left[j] + 1);
}
}
}
}
// 计算right数组
for (int i = index + 1; i < n; i++) {
for (int j = i - 1; j >= index; j--) {
if (positions[j] < positions[i]) {
int diff = heights[j] - heights[i];
if (diff <= 0 || diff > positions[i] - positions[j]) {
right[i] = Math.max(right[i], right[j] + 1);
}
}
}
}
// 计算结果
int maxCount = 1;
for (int i = 0; i < n; i++) {
maxCount = Math.max(maxCount, left[i] + right[i] - 1);
}
return maxCount;
}
public static void main(String[] args) {
int[] positions = {1, 3, 7, 8, 9};
int[] heights = {1, 2, 6, 4, 3};
int index = 2;
int maxCount = knockDown(positions, heights, index);
System.out.println("最多能打倒的骨牌数:" + maxCount); // 预期输出结果为4
}
}
```
以上代码中,我们使用了动态规划的思想,分别计算了从每个位置往左和往右最多能打倒的骨牌数,然后取两者之和再减1即为任意推倒一块骨牌,最多能打倒的骨牌数。时间复杂度为O(n^2),空间复杂度为O(n)。