HDURevenge of Segment Tree（第二长的递增子序列）

HDURevenge of Segment Tree（第二长的递增子序列）

题目链接

题目大意:这题是求第二长的递增子序列。

解题思路：用n^2的算法来求LIS，可是这里还要记录一下最长的那个序列是否有多种组成方式，假设>= 2, 那么第二长的还是最长的LIS的长度，否则就是LIS - 1；

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1005;

int l[maxn], c[maxn];

int arr[maxn];

int main () {

    int T, n;

    scanf ("%d", &T);

    while (T--) {

        scanf ("%d", &n);

        for (int i = 1; i <= n; i++)

            scanf ("%d", &arr[i]);

        for (int i = 1; i <= n; i++)

            l[i] = c[i] = 1;

        int ans = 1;

        for (int i = 2; i <= n; i++) {

            for (int j = 1; j < i; j++) {

                if (arr[i] > arr[j]) {

                    if (l[j] + 1 > l[i]) {

                        l[i] = l[j] + 1;

                        c[i] = c[j];

                    } else if (l[j] + 1 == l[i])

                        c[i] = 2;//之前直接加上c[j],结果会int溢出。导致错误。

                }

            }

            ans = max (ans, l[i]);

        }

        int cnt = 0;

        for (int i = 1; i <= n; i++)

            if (l[i] == ans)

                cnt += c[i];

        if (cnt > 1)

            printf ("%d\n", ans);

        else

            printf ("%d\n", ans - 1);

    }

    return 0;

}