【题解】B2097 最长平台

Dimly_dust · 2021-07-10 19:41:04 · 题解

Part 1

观察题目后可得结论（自行证明）：

• 两个相邻平台中必定交界处的两个元素不同

有了这个结论题目就好做多了，下面介绍几种做法。

Algorithm 1

采用 \texttt{DP} 算法，规定 \texttt{f[i]} 为到 \texttt{i} 元素 \texttt{a[i]} 的平台长度，可得：

时间复杂度 \mathcal{O(n)}，空间复杂度 \mathcal{O(n)} 。

Code

#include <bits/stdc++.h>
using namespace std;
int f[105],a[105];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
int main()
{
    int n=read(),maxn=-1;
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[i-1]) f[i]=f[i-1]+1; //不用处理f[0]是因为a是大于0的正整数
        else
        {
            f[i]=1;
            maxn=max(maxn,f[i-1]);
        }
    }
    printf("%d",maxn);
    return 0;
}

Algorithm 2

那么我们思考一下，怎么优化呢？

可以发现每一个平台长度 \texttt{f[i]} 只要是 \texttt{a[i],\ a[i-1]} 不相等时就是独立的，我们可以把 \texttt{f[i]} 的空间节约下来。

既然计算只涉及到 \texttt{a[i],\ a[i-1]} ，那么我们也同样可以用此方法节约空间。

时间复杂度 \mathcal{O(n)}，空间复杂度 \mathcal{O(1)} 。

Code

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
int main()
{
    int n=read(),maxn=-1,len=1;
    int k=read();
    for(int i=2; i<=n; i++)
    {
        int j=read();
        if(j==k) len++;
        else
        {
            maxn=max(maxn,len);
            len=1;
        }
        k=j;
    }
    printf("%d",maxn);
    return 0;
}