不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

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

结果就一不小心看到了这个充满回忆的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