求给定Q连续序列[1~N]最大计数值但仅使用q-2的规划问题

Question

下面是编程问题https://acm.cs.nthu.edu.tw/problem/12673/

我已经试了好几天了，但没能得出一个明确的解决方案。

简而言之，问题是：

在从1到n的一行中有n个区段。

这里有Q兵，对于第一个士兵，他可以从L_i区守卫到R_i(1 <= i <= q)。

如果至少有一名士兵守卫该部分，则该部分被守卫。

你只能雇佣q-2士兵。

你需要找到最大数量的部分，可以通过雇用q-2士兵从Q士兵。

我试着把每个士兵按正确的顺序排列，数一数每个士兵的唯一守卫数，然后根据其唯一的守卫数选择q-2士兵。但是输出是不对的。

下面是我的代码，其中有一些问题：

#include <stdio.h>
#include <stdlib.h>

typedef struct man
{
    int unique_defence_num;
    int defence_num;
    int L;
    int R;
    int id;
} man;
int cmpfunc(const void *a, const void *b)
{
    return (((man *)a)->L - ((man *)b)->L);
}
int cmpfunc2(const void *a, const void *b)
{
    return (((man *)a)->unique_defence_num - ((man *)b)->unique_defence_num);
}

int main()
{
    int testcase;
    int wall, soldier;
    scanf("%d ", &testcase);
    while (testcase--)
    {
        scanf("%d %d", &wall, &soldier);
        man *arr = (man *)malloc(soldier * sizeof(man));
        int i = 0, j = soldier;
        while (j--)
        { //O(soldier)
            scanf("%d %d", &(arr[i].L), &(arr[i].R));
            arr[i].defence_num = arr[i].R - arr[i].L + 1;
            arr[i].unique_defence_num = 0;
            arr[i].id = i;
            i++;
        }
        qsort(arr, soldier, sizeof(arr[0]), cmpfunc); //O(s*log(s))
        printf("the soldier id sequence after sorting on L:\t");
        for (int j = 0; j < soldier; j++)
            printf("%d ", arr[j].id);
        printf("\n");

        int *defencable = (int *)malloc(wall * sizeof(int));
        for (int j = 0; j < wall; j++)
            defencable[j] = 0;
        j = 0;
        while (j < soldier)
        { //O(s*w)
            int count = 0;
            for (int i = arr[j].L; i <= arr[j].R; i++)
            {
                if (j == 0) //first soldier
                {
                    if (i < arr[j + 1].L)
                    {
                        count++;
                        defencable[i] = 1; //the i-th gate can be guard
                    }
                }
                else if (j == soldier - 1) //last soldier
                {
                    if (i > arr[j - 1].R)
                    {
                        count++;
                        defencable[i] = 1; //the i-th gate can be guard
                    }
                }
                else if (defencable[i] == 0) // middle soldiers
                {
                    if (i > arr[j - 1].R && i < arr[j + 1].L)
                    {
                        count++;
                        defencable[i] = 1; //the i-th gate can be guard
                    }
                }
            }
            arr[j].unique_defence_num = count;
            j++;
        }
        qsort(arr, soldier, sizeof(arr[0]), cmpfunc2); //O(s*log(s))
        printf("the soldier id sequence after sorting on unique_defence_num:\t");
        for (int j = 0; j < soldier; j++)
            printf("%d ", arr[j].id);
        printf("\n");
        printf("the correspoonding unique_defence_num:\t");
        for (int j = 0; j < soldier; j++)
            printf("%d ", arr[j].unique_defence_num);
        printf("\n");
        for (int j = 0; j < wall; j++)
            defencable[j] = 0;
        int max = 0;
        for (int j = 2; j < soldier; j++)
        { //exclude the first two soldier that do not contribute to the defence
            for (int i = arr[j].L; i <= arr[j].R; i++)
            {
                if (defencable[i] == 0)
                {
                    defencable[i] = 1; //the i-th gate can truely be guard
                    max++;
                }
            }
        }
        printf("%d\n\n", max);
        free(arr);
    }
}

测试用例输入：

3
7 5
1 4
4 5
5 6
6 7
3 5

4 3
1 1
2 2
3 4

4 4
1 1
2 2
2 3
3 4

我的代码输出(有问题)：

the soldier id sequence after sorting on L:     0 4 1 2 3
the soldier id sequence after sorting on unique_defence_num:    4 1 2 3 0 
the correspoonding unique_defence_num:  0 0 0 1 2
maximum defencable wall: 6

the soldier id sequence after sorting on L:     0 1 2
the soldier id sequence after sorting on unique_defence_num:    1 0 2 
the correspoonding unique_defence_num:  1 1 2
maximum defencable wall: 1

the soldier id sequence after sorting on L:     0 2 1 3
the soldier id sequence after sorting on unique_defence_num:    2 1 0 3
the correspoonding unique_defence_num:  0 0 1 2
maximum defencable wall: 2

所需的输出是(没有调试信息)：

7
2
3

我不知道该如何解决这个问题，蛮力的方法不起作用和TLE。

我认为最难的部分是如何挑选两个不想要的士兵，因为两个可能相互依赖，可能是许多组合.

(这是我关于堆栈溢出的第一个问题，如果对问题或问题的方式有任何建议或提示，非常感谢。)

Answer 1

欢迎来到堆栈溢出。我给出的是一个通用算法而不是代码。

我用的是q=number of soldiers和n=length of wall的符号

将问题分解为2种情况:一种有子集，另一种没有

案例A:首先遍历每一对士兵并检查子集。(L[i]>L[j] && R[i]<R[j])。如果找到任何子集，请移除该士兵(应采取O(q^2))。消灭另一名士兵的问题变得微不足道。

案例B:，我的回答将更多地集中在第二种情况，即找不到子集。

1. 根据O(qlogq)中的左索引对所有士兵进行排序。对于每个士兵，在O(q*n).
2. Then，中计算他/她守卫的唯一墙的数量(unique_defence_num)，在O(q*n + q*q)中的排序士兵数组上迭代如下：

    for soldier i in 1 to q:
        for soldier j in i+1 to q:
            if(j==i+1):
                //Calculate unique positions guarded by these 2 combined in `O(n)`
            else:
                //unique positions guarded by these 2 combined = sum of both their "unique_defence_num"s (Can be found in O(1))
            update value of soldier_pair_with_least_contribution 

O(n)

1. 移除这2名士兵并输出所需的一切

算法的关键部分:给定按左索引排序的间隔(例如没有子集)，唯一组合部分可以表示为它们各自唯一部分的总和，条件是在这两个线段的开始之间至少有一个其他线段开始。这可以从以下事实中得到:任何时间间隔从后开始也会在晚些时候结束。

请注意，移除一名士兵和另一名士兵的贪婪方法并不总是有效的。以{1,5，6,10，2,9}为例