题解

这道题目要求我们在一队士兵中，找到最少需要删除多少个士兵，使得剩下的士兵可以看到至少一个端点（左端或右端）。士兵的可见性是根据其身高来决定的：只有比它身高高的士兵会阻挡它的视线。

解题思路

1. 问题理解：

   • 给定一个由 n 个士兵组成的队列，每个士兵有一个身高。
   • 目标是找到一个子队列，使得子队列中每个士兵都能看到至少一个端点。我们要通过删除尽可能少的士兵来达到这个目标。

2. 可见性条件：

   • 每个士兵的可见性由其前面和后面的士兵高度决定。只有在该士兵的身高在其视线内不被任何与其身高相等或更高的士兵挡住时，才能看到某个端点。

3. 子序列问题：

   • 这可以转化为求解两个最长单调子序列（分别从前到后和从后到前）的问题。

     • 从左到右的最长上升子序列：这表示士兵的身高从左端开始的最大子序列，其中每个士兵能看到左端。
     • 从右到左的最长下降子序列：这表示士兵的身高从右端开始的最大子序列，其中每个士兵能看到右端。

4. 动态规划：

   • 用动态规划来求解这两个子序列问题：

     • dp1[i] 表示以第 i 个士兵为结尾的最长上升子序列的长度。
     • dp2[i] 表示以第 i 个士兵为起始的最长下降子序列的长度。

5. 最终解：

   • 通过计算每个士兵能看到左端和右端的最大子序列长度之和，减去 1（因为该士兵被计算了两次），得到最少需要删除的士兵数量。

代码实现

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int dp1[1100], dp2[1100]; // dp1[] 从前往后；dp2[] 从后往前
double s[1100];
int n;

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%lf", &s[i]);
            dp1[i] = 1; // 初始化
            dp2[i] = 1;
        }
        int len = 0; // 剩余士兵的最大长度
        
        // 求最长上升子序列 dp1[]
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i - 1; j++) {
                if (s[j] < s[i])
                    dp1[i] = max(dp1[i], dp1[j] + 1);
            }
        }

        // 求最长下降子序列 dp2[]
        for (int i = n; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                if (s[j] < s[i])
                    dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }

        // 处理重复值的情况
        for (int i = 1; i <= n; i++) {
            int flag = 1; // 标记最高点
            // 找到i前面的离i最近的与s[i]相等的点，更新dp1[i]
            for (int j = i - 1; j >= 1; j--) {
                if (s[j] == s[i]) {
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                    flag = 0;
                    break;
                }
            }
            // 找到i后面的离i最近的与s[i]相等的点，更新dp2[i]
            for (int j = i + 1; j <= n; j++) {
                if (flag && s[j] == s[i]) {
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                    break;
                }
            }
            len = max(len, dp1[i] + dp2[i] - 1); // 更新最大长度
        }

        // 输出最小删除的长度
        printf("%d\n", n - len);
    }
    return 0;
}

代码解释

1. 输入处理：

   • 首先读取测试数据的个数，然后对每组测试数据读取士兵的数量 n 和士兵的身高数据。

2. 初始化：

   • dp1[i] 初始化为 1，表示以第 i 个士兵为结尾的最长上升子序列的长度。
   • dp2[i] 初始化为 1，表示以第 i 个士兵为起始的最长下降子序列的长度。

3. 动态规划计算：

   • 通过两层循环，计算从左到右的最长上升子序列（dp1[]）和从右到左的最长下降子序列（dp2[]）。

4. 重复值处理：

   • 对于重复的身高，我们需要特别处理：检查是否有相同身高的士兵，在前后方向的最长子序列的计算中进行更新。

5. 最终计算：

   • 通过 dp1[i] + dp2[i] - 1 来计算每个士兵能看到两个端点的最大子序列长度，并更新最大长度 len。
   • 最终输出需要删除的士兵数，即 n - len。

复杂度分析

• 时间复杂度：

  • 计算 dp1[] 和 dp2[] 都需要双重循环，因此时间复杂度为 $O(n^2)$。
  • 对于最大 $n = 1000$，最坏情况下的时间复杂度是 $O(10^6)$，在给定的时间限制内是可以接受的。

• 空间复杂度：

  • 我们使用了三个数组 dp1[]、dp2[] 和 s[]，所以空间复杂度是 $O(n)$。

示例

输入：

1
8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2

输出：

4

结论

这道题目通过动态规划求解最长上升子序列和最长下降子序列的组合，解决了士兵能否看到端点的问题。通过对每个士兵计算最大可见子序列的长度，得出最少需要删除的士兵数。