[UOJ#246][UER#7C]套路

Description

给出n个在[1,m]范围内的数，你需要从中至少选k个连续的数。
定义s(l,j)表示[l,r]这个区间中的数两两之间差值绝对值的最小值，你需要让选择的区间[i,j]的s(i,j)*(j-i)最小。
求这个最小值。
n,m<=2*10^5

Solution

现在我们要想想如何求出一个区间的s值。
一个显然的想法是在区间长度x较小时，用F[i][j]表示i为左端点，且长度为j的区间的s值。
转移也很显然。
时间复杂度$O(nx)$
那么长度较大时呢？
根据鸽巢原理，一个长度为x的区间的s值最大是$mover {x-1}$!
那么我们可以枚举这个值j，从左往右扫一遍，然后更新以当前点为右端点且s值为j的左端点的值。这个东西可以用每个数最后出现的位置来维护。。。
时间复杂度$O(n{mover x})$
看到这你想到了什么？
平衡规划！！
我们设一个常数S，当x小于S时用第一种方法，当x大于S时用第二种方法。
显然$S=sqrt m$时最优
时间复杂度$O(nsqrt m)$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=2e5+5,S=555;
int n,m,k,a[N],f[N],last[N],l[N];
ll ans;
int main() {
    scanf("%d%d%d",&n,&m,&k);
    fo(i,1,n) scanf("%d",&a[i]);
    memset(f,127,sizeof(f));
    fo(len,1,S) fo(i,1,n-len) {
        f[i]=min(min(f[i+1],f[i]),abs(a[i]-a[i+len]));
        if (len>=k-1) ans=max(ans,(ll)f[i]*len);
    }
    fo(i,0,m/S) l[i]=1;
    fo(i,1,n) {
        fo(j,0,m/S) {
            if (i-l[j]>=k-1) ans=max(ans,(ll)(i-l[j])*j);
            l[j+1]=max(l[j+1],l[j]);
            if (a[i]-j>=1) l[j+1]=max(l[j+1],last[a[i]-j]);
            if (a[i]+j<=m) l[j+1]=max(l[j+1],last[a[i]+j]);
        }
        last[a[i]]=i+1;
    }
    printf("%lldn",ans);
}

最后

以上就是超级小兔子为你收集整理的[UOJ#246][UER#7C]套路的全部内容，希望文章能够帮你解决[UOJ#246][UER#7C]套路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。