F - Almost Sorted Array HDU - 5532

We are all familiar with sorting algorithms: quick sort, merge sort, heap sort, insertion sort, selection sort, bubble sort, etc. But sometimes it is an overkill to use these algorithms for an almost sorted array.
We say an array is sorted if its elements are in non-decreasing order or non-increasing order. We say an array is almost sorted if we can remove exactly one element from it, and the remaining array is sorted. Now you are given an array a1,a2,…,an , is it almost sorted? Input The first line contains an integer T indicating the total number of test cases. Each test case starts with an integer n in one line, then one line with n integers a1,a2,…,an.
1≤T≤2000 2≤n≤105 1≤ai≤105 There are at most 20 test cases with n>1000 . Output For each test case, please output “YES ” if it is almost sorted. Otherwise, output “NO ” (both without quotes). Sample Input
3 3 2 1 7 3 3 2 1 5 3 1 4 1 5
Sample Output
YES YES NO 제목: 임의의 요소를 삭제한 후에 이 서열이 점증 서열이나 점감 서열인지 판단하는 수조를 드리겠습니다.일반 사고방식: 무모한 모든 상황 (어쨌든 나는 무모한 것이 아니다) dalao 사고방식: LIS는 최장 상승 서열과 최장 하강 서열을 구한다...n or n-1인지 아닌지 판단하고 어떻게 보면 일리가 있는 것 같아서 두드렸어요. AC 코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f// int ， 2 int

int a[MAXN], dpa[MAXN], dpb[MAXN], b[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(dpa, 0, sizeof(dpa));
        memset(dpb, 0, sizeof(dpb));
        int n, len = 1, cnt = 1;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            b[n-i+1] = a[i];
        }
        dpa[1] = a[1];
        dpb[1] = b[1];
        for (int i = 2; i <= n; ++i)
        {
            if (a[i] >= dpa[len])
                dpa[++len] = a[i];
            else
            {
                int m = upper_bound(dpa + 1, dpa + 1 + len, a[i]) - dpa;
                dpa[m] = a[i];
            }
            if (b[i] >= dpb[cnt])
                dpb[++cnt] = b[i];
            else
            {
                int tem = upper_bound(dpb + 1, dpb + 1 + cnt, b[i]) - dpb;
                dpb[tem] = b[i];
            }
        }
        if (cnt == n || cnt == n - 1 || len == n || len == n - 1)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

나는 n번의 코드를 썼다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define MAXN 100005
#define INF 0x3f3f3f3f// int ， 2 int

int a[MAXN], dpa[MAXN], dpb[MAXN], b[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(dpa, 0, sizeof(dpa));
        memset(dpb, 0, sizeof(dpb));
        int n, len = 1, cnt = 1;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            b[n-i+1] = a[i];
        }
        dpa[1] = a[1];
        dpb[1] = b[1];
        for (int i = 2; i <= n; ++i)
        {
            if (a[i] >= dpa[len])
                dpa[++len] = a[i];
            else
            {
                int m = lower_bound(dpa + 1, dpa + 1 + len, a[i]) - dpa;
                dpa[m] = a[i];
            }
            if (b[i] >= dpb[cnt])
                dpb[++cnt] = b[i];
            else
            {
                int tem = lower_bound(dpb + 1, dpb + 1 + cnt, b[i]) - dpb;
                dpb[tem] = b[i];
            }
        }
        cout << len << ' ' << cnt << '
';
        if (cnt == n || cnt == n - 1 || len == n || len == n - 1)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

어쩔 수 없이 이 두 코드는:lower_bound 및 upper_bound의 차이...제가 전에 쳤던 LIS는 다 lower로 했어요.bound의, 그래서 나는 미친 듯이 wa를 한 후에 문제를 찾으러 갔다. 그리고 고치자마자 푸르러졌다. 나는...그럼 lower_bound 및 upper_bound의 차이는 도대체 어디에 있는 거지?!블로그 참조:lower_bound 및 upper_bound의 차이