胡广.top

最长不下降子数列->从o(n^2)到o(n*logN)

优化方法来源于洛谷的题解 另外原题在此

可以说是动态规划的模板之一了。

从不会到解出来

动态规划的两个要点，当前状态与转移方程。

对于第一问

当前状态取处理到第i颗导弹。转移方程
d(i)=\max^{i-1}_{j=0}{d(j)(j满足H[j]\le H[i])}+1
表示当前找到的最长列。这样子的复杂度明显是n^2。

对于第二问

我的策略不同，但是后来证明，只需少量优化，这个策略可以跑到n \cdot log(n)。我模拟了采用n套系统，对于每颗导弹，当前高度不低于它的系统中最低的那一套来拦截。大体上，这应该也是一个n^2算法。

从会到快

当我在写那份n^2的代码的时候，题目底下那句n \cdot log(n)得200分引起了我的注意。

但是动态规划是得不到log(n)的，回想一下，log(n)通常出现在什么地方呢？二分、分治都是把n变成log(n)的好方法。

我们来假设一个函数f(x)，定义f(x)的返回值是
\max_{i=x-1}^{i=Records-1}{H[i]}(i满足d(i)=x)
取max是因为，对于导弹问题，高一些总归好。

很明显，f(x)是单调减的函数。可以二分了。

但是，明显不能用d(i)去求f(x)，那样反而增加复杂度。我们要做的是开一个数组F[x],先F[0]=H[0],然后for(int i=0;i<Records)，在0 \sim MaxLen+1当中二分得到一个mid满足F[mid]且这个mid尽可能大，执行

F[mid]=Record[i];
MaxLen=max(MaxLen,mid);

对于第二问，只需优化决定那一套系统来拦截的代码为二分即可完成优化。

AC！

代码

n^2

#include<stdio.h>
const int MAX_N = 100007;
const int MAX_H = 50007;
int Record[MAX_N];
int Records = 0;
int DP_mem[MAX_N];//-1:NOT Caulated
int systems[MAX_N];
int SystemNeeded;
int MaxLen;
inline int max(int a, int b)
{
    return a > b ? a : b;
}
int DP(int i)
{
    if (DP_mem[i]!=-1)
    {
        return DP_mem[i];
    }
    else
    {
        int MAX = 0;
        for (size_t j = 0; j < i; j++)
        {
            if (Record[j]>=Record[i])
            {
                MAX = max(MAX, DP(j));
            }
        }
        MAX++;
        return DP_mem[i] = MAX;
    }
}
int main(void)
{
    Records = 0;
    while (scanf("%d", &Record[Records]) != EOF)
    {
        DP_mem[Records] = -1;
        systems[Records] = MAX_H;
        Records++;
    }
    SystemNeeded = 0;
    MaxLen = 0;
    for (size_t i = 0; i < Records; i++)
    {
        int j;
        for (j = 0; systems[j] < Record[i]; j++);
        systems[j] = Record[i];
        SystemNeeded = max(SystemNeeded, j);
        MaxLen = max(DP(i), MaxLen);
    }
    printf("%d\n%d\n", MaxLen, SystemNeeded+1);
    return 0;
}

n \cdot log(n)

#include<stdio.h>
const int MAX_N = 100007;
const int MAX_H = 50007;
int Record[MAX_N];
int Records = 0;
int systems[MAX_N];
int MaxHightByLen[MAX_H];
int SystemNeeded;
int MaxLen;
inline int max(int a, int b)
{
    return a > b ? a : b;
}
int main(void)
{
    Records = 0;
    while (scanf("%d", &Record[Records]) != EOF)
    {
        systems[Records] = MAX_H;
        Records++;
    }
    SystemNeeded = 0;
    MaxLen = 0;
    MaxHightByLen[0] = MAX_H;
    for (size_t i = 0; i < Records; i++)
    {
        int j;
        int left = 0, right = SystemNeeded+1;
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (systems[mid] >= Record[i])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
            j = left;
            systems[j] = Record[i];
            SystemNeeded = max(SystemNeeded, j);
        }
        int left = 0, right = MaxLen + 1;
        while (left<right)
        {
            int mid = (left + right) / 2;
            if (MaxHightByLen[mid]<Record[i])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
            MaxHightByLen[right] = Record[i];
            MaxLen = max(MaxLen, right);
        }
    }
    printf("%d\n%d\n", MaxLen, SystemNeeded+1);
    return 0;
}

Nemo

,
,