使用c语言实现这个代码
时间: 2024-04-05 14:29:58 浏览: 22
好的,以下是使用 C 语言实现上述算法的代码:
```c
#include <stdio.h>
#define MAX_N 10000
int dp[MAX_N]; // dp数组表示以nums[i]结尾的最长上升子序列长度
int heights[MAX_N];
int intervals[MAX_N][2]; // intervals数组记录拦截系统能拦截的导弹高度区间
int lis(int n) {
int max_len = 1, start_idx = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (heights[j] < heights[i]) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
if (dp[i] > max_len) {
max_len = dp[i];
start_idx = i;
}
}
return start_idx;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &heights[i]);
}
int start_idx = lis(n);
int max_len = dp[start_idx];
int num_systems = max_len;
intervals[0][0] = start_idx;
intervals[0][1] = heights[start_idx];
int idx = 0;
for (int i = start_idx - 1; i >= 0; i--) {
if (dp[i] == max_len - 1 && heights[i] < intervals[idx][1]) {
idx++;
intervals[idx][0] = i;
intervals[idx][1] = heights[i];
max_len--;
}
}
printf("最少需要%d套导弹拦截系统\n", num_systems);
printf("可拦截的导弹高度区间为:");
for (int i = idx; i >= 0; i--) {
printf("[%d, %d] ", intervals[i][0], intervals[i][1]);
}
printf("\n");
return 0;
}
```
在上述代码中,我们先读入导弹高度序列,然后调用 lis 函数求出最长上升子序列的起始位置 start_idx 和长度 max_len。接着,我们将 intervals 数组的第一个元素初始化为 start_idx 和 heights[start_idx],然后从后往前遍历 dp 数组,找到所有比 max_len 小 1 的元素,并且高度比 intervals 中最后一个元素小的位置,将这些位置和高度加入 intervals 数组中。最后输出 num_systems 和 intervals 即可。
希望可以帮到你!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)