在某个神奇的下午,收到一个垃圾邮件(至少被邮件系统当成了垃圾邮件)。

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

果然好久没碰算法,脑子是会生锈的。

第一题大水,懒得写。

第二题伤了很久的脑筋,想出了一个算法结果ultramanhu基于此想出了个更容易理解更容易实现的方法。

以我这种懒人的本性,必须是也懒得写得。

于是意思意思就干上了第三题。题目见这里 http://wenda60.com/programs/view/id-550.html

不得不说,现在不如从前,想出这题的解法还是费了一点时间的。不过这个题目太厚道了,能有的trick在sample里都有了。

这个题是问最少改多少个数字能让输入的数字递增,并且第一个数字不小于1。

很显然一个增子序列嘛。但是又有一点点地不同,应为最终是修改数字,而且数字不能重的,所以增子序列里两个相邻的值还和这两个数之间的数字个数有关。

就是这两个值的相差必须大于之间的数字个数。这里很容易就想到给最长增子序列变种,判断因素加上距离权值;

第二个条件是第一个值必须大于等于1。我想到的简单地做法是,在序列前面加一个0。轻松加愉快啊。

但是最长增子序列的算法是会重定向最佳值的,所以在执行检测的时候注意子序列一定要选0就OK了。

上代码:

#include <cstdio>
#include <iostream>

typedef int LISTYPE;

#define LISMAXN 100005

LISTYPE lR[LISMAXN];

int LIScmp(int a, int b, LISTYPE list[])
{
    return list[a] + b - a <= list[b];
}

int LISLength(LISTYPE list[], int n)
{
    int length = 1;
    
    lR[0] = 0;

    for (int i = 1; i < n; i++)
    {
        //二分查找,复杂度 log(n)
        int b, e, m;
        b = 0;
        e = length - 1;
        while (b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if (LIScmp(lR[m], i, list))
                b = m + 1;
            else
                e = m - 1;
        }

        if (0 == b) 
            continue;

        lR[b] = i;
        if (b >= length)
            length++;
    }
    return length;
}

LISTYPE LOri[LISMAXN];

int main() {
    int n;
    scanf("%d", &n);

    while (n-- > 0){
        int size;
        scanf("%d", &size);
        LOri[0] = 0;
        for (int i = 1; i <= size; ++i){
            scanf("%d", &LOri[i]);
        }

        printf("%d\n", size + 1 - LISLength(LOri, size + 1));
    }
    return 0;
}

不知道为什么,这个代码上去以后显示PE,我也不知道PE在哪了。(我试了各种乱加减空格和换行,都木有用,全PE。故意写错一个数,就变WA了,所以应该真的是PE) 不过反正结果对了后面就懒得再研究了,反正现在又不参赛

PS: 最长增子序列用得是以前写得模板:https://www.owent.net/2009/74.html