题目传送门

$暴力很好打$
有没有人性，才给7分！！！
$看了一下没有给太大的值域，显然是要从值域着手$
$对于子任务3（和正解有关）可以用一个dp解决$
$dp[i][j]表示以i为左端点，j为右端点的最小的差值$
$dp[i][j]=Min(dp[i-1][j],dp[i][j-1],abs(a[j]-a[i]))$
$对于子任务4，可以根据抽屉原理，对于小于m区间直接的直接暴力，大于的直接输出0(因为值域，还是整数，肯定有两个值相同)$
$根据抽屉原理，很显然可以发现一个结论：如果一个区间的长度为x，那么最小差值不超过m/x$
$根据这个原理，可以直接将答案分开统计，对于区间小于\sqrt{m}的直接用子任务3的方法统计$
$对于大于\sqrt{m}，可以发现相减值域是一个比较小的值，从这方面下手$
$r[i]表示i这个值出现的最大的坐标，ch[i]表示差值为i的最大坐标$
$枚举右端点，这两个就很好转移了，具体看代码$

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
int n,m,k,a[N],s,r[N];
int ch[N];ll f[N],ans;
int main()
{
	freopen("blueming.in","r",stdin);
	freopen("blueming.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	memset(f,127,sizeof(f));
	for(int i=1;i<=n;i++)
	  scanf("%d",&a[i]);
	s=floor(sqrt(m));
	for(int i=2;i<=s;i++)
	  for(int j=1;j+i-1<=n;j++){
		f[j]=min(f[j],min(f[j+1],1ll*abs(a[j]-a[j+i-1])));
		if(i>=k)ans=max(ans,f[j]*(i-1));
      }
    for(int i=1;i<=n;i++){
    	int up=m/s;
    	for(int j=0;j<=up+1;j++){
    		ll u=a[i]+j,v=a[i]-j;
    		if(j>=1)ch[j]=max(ch[j],ch[j-1]);
    		if(u<=m)ch[j]=max(ch[j],r[u]);
    		if(v>=1)ch[j]=max(ch[j],r[v]);
    		if(i-ch[j]+1>max(s,k))ans=max(ans,1ll*(i-ch[j]-1)*(j+1));
		}r[a[i]]=i;
	}
    printf("%lld",ans);return 0;
}

最后

以上就是要减肥苗条为你收集整理的uoj套路题目传送门的全部内容，希望文章能够帮你解决uoj套路题目传送门所遇到的程序开发问题。

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