【UOJ#246】套路(动态规划)
题面
题解
假如答案的选择的区间长度很小,我们可以做一个暴力\(dp\)计算\(s(l,r)\),即\(s(l,r)=min(s(l+1,r),s(l,r-1),abs(a_r-a_l))\)。
我们发现\(s(l,r)\le \frac{m}{r-l+1}\),那么当长度足够大的时候\(s(l,r)\)的取值很小。 所以我们对于询问分治处理,当长度小于\(\sqrt m\)时,直接\(dp\)计算贡献。 否则,当长度大于\(\sqrt m\)时,枚举\(s(l,r)\)的值,对于每个右端点计算其合法的最大左端点。 复杂度\(O(n\sqrt m)\)#include#include #include #include using namespace std;#define ll long long#define MAX 200200inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}ll ans;int a[MAX],n,m,k,blk,s[MAX],lst[MAX],pos[MAX];int main(){ n=read();m=read();k=read();blk=sqrt(m)+1; for(int i=1;i<=n;++i)a[i]=read(),s[i]=m; for(int l=2;l<=blk;++l) { for(int j=1;j+l-1<=n;++j)s[j]=min(abs(a[j]-a[j+l-1]),min(s[j],s[j+1])); if(l>=k)for(int j=1;j+l-1<=n;++j)ans=max(ans,1ll*(l-1)*s[j]); } for(int i=1;i<=n;lst[a[i]]=i,++i) for(int j=0,r=0;j<=blk;++j) { if(a[i]-j>=1)pos[j]=max(pos[j],lst[a[i]-j]); if(a[i]+j<=m)pos[j]=max(pos[j],lst[a[i]+j]); if(pos[j]>r&&i-r>=k)ans=max(ans,1ll*(i-r-1)*j); r=max(r,pos[j]); } printf("%lld\n",ans); return 0;}