修改代码使之输出最长事件序列
时间: 2024-03-22 22:38:28 浏览: 16
可以使用深度优先搜索(DFS)来输出所有最长事件序列。修改后的代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int begin;
int end;
} Event;
int cmp(const void *a, const void *b) {
Event *e1 = (Event *) a;
Event *e2 = (Event *) b;
return e1->end - e2->end;
}
void dfs(Event *events, int *dp, int *pre, int *res, int pos, int end, int max_len) {
if (pos == -1) {
for (int i = 0; i < max_len; i++) {
printf("%d ", events[res[i]].begin);
}
printf("\n");
return;
}
for (int i = end; i >= 0; i--) {
if (dp[i] == pos + 1 && (i == 0 || events[i].begin >= events[pre[i]].end)) {
res[pos] = i;
dfs(events, dp, pre, res, pos - 1, pre[i], max_len);
}
}
}
int main() {
int n;
scanf("%d", &n);
Event *events = (Event *) malloc(sizeof(Event) * n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &events[i].begin, &events[i].end);
}
qsort(events, n, sizeof(Event), cmp);
int *dp = (int *) malloc(sizeof(int) * n);
int *pre = (int *) malloc(sizeof(int) * n);
int *res = (int *) malloc(sizeof(int) * n);
memset(dp, 0, sizeof(int) * n);
memset(pre, -1, sizeof(int) * n);
dp[0] = 1;
int max_len = 1, end = 0;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (events[i].begin >= events[j].end && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > max_len) {
max_len = dp[i];
end = i;
}
}
dfs(events, dp, pre, res, max_len - 1, end, max_len);
free(res);
free(events);
free(dp);
free(pre);
return 0;
}
```
输出结果为:
```
0 1 5 8 10
0 2 5 8 10
```
即两个最长事件序列分别为{0,1,5,8,10}和{0,2,5,8,10}。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)