LIS 2015百度之星初赛2 HDOJ 5256 序列变换

题意：中文题面

分析：LIS(非严格)：首先我想到了LIS，然而总觉得有点不对；每个数先减去它的下标，防止下面的情况发生：(转载)加入序列是1,2,2,2,3,这样求上升子序列是3，也就是要修改2个，但是中间的两个2，变化范围又不能超过（1,3）那么这样求的也就是不对的，但是减掉之后，相当于给中间重复的数留下了修改的空间。解释下为什么可以减而保持正确性：因为题目所求时严格递增，假设是2，3, 4，那么变成1, 1, 1，所以在LIS里非严格递增就可以了这也是为什么要在upper_bound的位置插入。另外：lower_bound返回第一个>=key的位置；upper_bound返回第一个>key的位置，这样相减才是key的个数

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <vector>

#include <queue>

#include <set>

using namespace std;

const int MAXN = 1e5 + 10;

const int INF = 0x3f3f3f3f;

int a[MAXN], d[MAXN];

int n;

int BinarySearch(int l, int r, int key)

{

    while (l <= r)

    {

        int mid = (l + r) / 2;

        if (key >= d[mid])    l = mid + 1;

        else    r = mid - 1;

    }

    return l;

}

int LIS(void)

{

    int len = 1, j;

    d[1] = a[1];

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

    {

        if (d[len] <= a[i])    d[++len] = a[i];

        else

        {

            j = upper_bound (d+1, d+1+len, a[i]) - d;        //返回第一个比a[i]大的位置

//            j = BinarySearch (1, len, a[i]);

            d[j] = a[i];

        }

    }

    return len;

}

int main(void)        //2015百度之星初赛2 HDOJ 5256 序列变换

{

    int t, cas = 0;    scanf ("%d", &t);

    while (t--)

    {

        scanf ("%d", &n);

        for (int i=1; i<=n; ++i)    {scanf ("%d", &a[i]);    a[i] -= i;}

        printf ("Case #%d:\n", ++cas);

        printf ("%d\n", n - LIS ());

    }

    return 0;

}

巴特西

LIS 2015百度之星初赛2 HDOJ 5256 序列变换

最新文章

热门文章