uoj#246. 【UER #7】套路（dp+分块？分类讨论？）然而我们全然不用枚举这个kf[i]=min(f[i],f[i-1])

45 阅读 0 评论 30 点赞

我是靠谱客的博主仁爱花生，最近开发中收集的这篇文章主要介绍uoj#246. 【UER #7】套路（dp+分块？分类讨论？）然而我们全然不用枚举这个kf[i]=min(f[i],f[i-1])，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

分析：
目前为止我只能理解dp部分

我就喜欢这种单纯不做作的题目
一看名字就明白了这道题的本质

中二的题目描述

很显然，我们的关键就是求出最小相似度
朴素算法n^4

如果我们现在有一个权值数组
显然，每一个数只可能与最邻近ta的数产生贡献
假设我们要求[i,j]之间的最小差距
那我们可以分成两部分[i,k],[k+1,j]
枚举k，取最小就可以了

但是这样的复杂度是n^3

然而我们全然不用枚举这个k

f[i][j]=abs(a[i]-a[j]) //i+1==j
f[i][j]=min{f[i+1][j],f[i][j-1],abs(a[i]-a[j])} //j-i>1

那还是n^2的，我们考虑能不能再次优化，去掉一维
空间：i的转移只牵扯到i和i-1，所以可以滚粗动数组
更进一步，因为当前状态i需要用到i+1的状态，所以我们倒着推
每次让当前的覆盖上一次的，上式中f[i][j]需要用到f[i+1][j]的结果现在的话直接继承
这样我们就可以在空间上直接去掉一维

f[i]=min(f[i],f[i-1])

注意转换成一维后f[i]表示的是终点在i的区间
这里写图片描述

最终算法：
实际上的基于dp的分类讨论
如果一个区间的长度是x，那么最小差值一定不超过m/(x-1)
那么我们设一个常数s=sqrt(n)
当x < s时，用算法一中的算法求解。
当x>=s时，那么最小差不会超过 m/(s-1)
我们枚举差值|z-x|<=m/(s-1) ,然后找到权值z最近一次出现的位置，然后计算答案
但是这样还是不够，我们必须保证两个位置之间不存在再小的差值
所以我们还需要一个数组g[i]来记录差值i最近一次出现的位置，
那么g[i]+1一定是在差值i+1或者更大的范围内，所以用（posx-g[i]-1)*(i+1)来更新答案

详尽题解

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define ll long long

using namespace std;

const int N=200002;
int n,m,k;
int pos[N],g[N];
ll f[N];
ll a[N],ans=0;

ll abs(ll x){if (x>0) return x; else return -x;}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    int s=floor(sqrt(n));
    memset(f,127,sizeof(f));   //INF
    for (int i=n;i>=1;i--)
    {
        for (int j=i+1;j<=min(n,i+s-1);j++)   //只做块内的
        {
            f[j]=min(f[j],f[j-1]);
            f[j]=min(f[j],abs(a[j]-a[i]));
            if (j-i+1>=k) ans=max(ans,(ll)(j-i)*f[j]);
        } 
    }
    for (int i=1;i<=n;i++)
    {
        int t=m/s;
        for (int j=0;j<=t+1;j++)
        {
            ll yy=a[i]+j;
            ll y=a[i]-j;
            if (j>=1) g[j]=max(g[j-1],g[j]);
            if (y>=1) g[j]=max(g[j],pos[y]);
            if (yy<=m) g[j]=max(g[j],pos[yy]);
            if (i-g[j]+1>max(s,k)) ans=max(ans,(ll)(i-g[j]-1)*(ll)(j+1));
        }
        pos[a[i]]=i;
    }
    printf("%lldn",ans);
    return 0;
}