DP优化之单调队列 专题
和单调队列有很多交集。。。
斜率优化理论不说多。一个式子至于变量i有关就极为belong[i];
就是DP方程满足了f[i]=max{belong1[j]+belong1[i]*belong2[j]+belong2[i]}
于是我们就说可以得到斜率belong1[i].以点(belong2[j],belong1[j])组成的凸壳。
求max就是保留上凸,min保留下凸。
---------------------------------------------------------------------
http://acm.hdu.edu.cn/showproblem.php?pid=3045
【HDU3045】【Picnic Cows】【斜率优化】
题目给定数列A,要求排序后,将这些数字分成若干组,每组至少m个数字。
f[i]=min{f[j]+(sum[i]-sum[j]-(i-j+1)*sum[j+1])}
f[i]=min{f[j]-sum[j]+(j-1)*sum[j+1]-i*sum[j+1]+sum[i]}
第一部分只与j有关,第三部分只与i有关,第二部分既与i有关又与i有关。
把-i当做斜率。(sum[j+1],f[j]-sum[j]+(j-1])*sum[j+1])插入凸壳中。因为是求min
所以保留下凸即可。
http://poj.org/problem?id=3709
【pku3709】【K-Anonymous Sequence】【斜率优化】
跟上面那题一样!
http://poj.org/problem?id=2018
【pku2018】【Best Cow Fences】【斜率优化】
题目给定一个一对点(i,f[i])求max{(f[i]-f[j])/(i-j)}
这时候其实是求一个最大斜率,保存一个下凸就可以了。
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1010
【HYOJ1010】【玩具装箱toy】【斜率优化】
题目给定一个序列C。一个长度L
把序列分成若干组使得所有组(sumC+numC-1-L)^2的总和最小。
numC表示该组中元素数,sumC表示该组中C的和。
f[i]=min{f[j]+sqr(sum[i]-sum[j]+(i-j-1)-L)}
f[i]=min{f[j]+sqr(sum[j]+j+1+L)-2*(sum[i]+i)*(sum[j]+j+1+L)+sqr(sum[i]+i)}
第一部分只与j有关,第三部分至于i有关,第二部分与i和j都有关。
以(2*(sum[i]+i))为斜率,以(sum[j]+j+1+L,f[j]+sqr(sum[j]+j+1+L))插入凸壳。
求最小值维护下凸即可。
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1911
【HYOJ1911】【RQNOJ533】【APIO2010】【特别行动部队】【斜率优化】
因为是2次函数,采用相同的方法可以分离系数。分成三部分。
【推荐!!!】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1713
这题很棒!!!
首先n^4的方法是显然的!
f[i][j]=max{f[i'][j']+a[i]*b[j]}
在稍加分析一下会发现
f[i][j]=max{max{f[i-1][j']+a[i]*b[j]},max{f[i'][j-1]}}
再采用斜率优化得到了n^2的方法。于是AC之~
#include<cstdio>
#define N 50010
#define LL long long
using namespace std;
LL que[N][2],sum[N],A[N],B[N],f[N],data[N];
LL n,last,L,tail;
LL sqr(LL x) {return x*x;}
LL cross(LL a[2],LL b[2],LL c[2])
{
return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0]);
}
void hulladd(LL x,LL y)
{
LL node[2];
node[0]=x;node[1]=y;
while (tail>=2 && cross(node,que[tail],que[tail-1])>=0) --tail;
++tail;que[tail][0]=node[0];que[tail][1]=node[1];
last <?= tail;
}
LL query(LL x)
{
while (last<tail && x*que[last][0]+que[last][1]>x*que[last+1][0]+que[last+1][1])
++last;
return que[last][0]*x+que[last][1];
}
int main()
{
freopen("HYOJ1010.in","r",stdin);
freopen("HYOJ1010.out","w",stdout);
scanf("%d%d",&n,&L);last=1;
for (LL i=1;i<=n;++i)
{
scanf("%d",&data[i]);
sum[i]=sum[i-1]+data[i];
}
for (LL i=0;i<=n;++i)
A[i]=sum[i]+i,B[i]=sum[i]+i+1+L;
for (LL i=1;i<=n;++i)
{
f[i]=sqr(sum[i]+i-L-1);
if (i>1)
{
hulladd(B[i-1],sqr(B[i-1])+f[i-1]);
f[i] <?= query(-2*A[i])+sqr(A[i]);
}
}
// for (LL i=1;i<=n;++i) printf("%d ** %d\n",i,f[i]);
printf("%I64d\n",f[n]);
}
#include<iostream>
#include<cstdio>
using namespace std;
#define N 100010
int que[N][2],a[N],sum[N],f[N];
int n,m,temp,tail,ans;
int cross(int a[2],int b[2],int c[2])
{
return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0]);
}
void hulladd(int x,int y)
{
int node[2];
node[0]=x;node[1]=y;
while (tail>=2 && cross(node,que[tail],que[tail-1])>=0) --tail;
++tail;que[tail][0]=x;que[tail][1]=y;
}
int query(int x,int y)
{
int tt=tail,node[2];
node[0]=x;node[1]=y;
while (tt>=2 && cross(node,que[tt],que[tt-1])>=0) --tt;
return 1000*(y-que[tt][1])/(x-que[tt][0]);
}
int main()
{
freopen("pku2018.in","r",stdin);
freopen("pku2018.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
for (int i=m;i<=n;++i)
{
f[i]=1000*sum[i]/i;
// printf("%d %d \n",i,f[i]);
if (i>m)
{
hulladd(i-m,sum[i-m]);
temp=query(i,sum[i]);
if (temp>f[i]) f[i]=temp;
}
// printf("%d %d \n",i,f[i]);
}
for (int i=m;i<=n;++i)
{
// printf("%d %d\n",i,f[i]);
if (f[i]>ans) ans=f[i];
}
printf("%d",ans);
return 0;
}
#include<iostream>
#include<cstdio>
#define N 400010
#define LL long long
using namespace std;
LL tail,a[N],que[N][2],sum[N],n,m,last,f[N],i,j,t;
LL cross(LL a[2],LL b[2],LL c[2])
{
return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0]);
}
void hulladd(LL x,LL y)
{
LL node[2];
node[0]=x;node[1]=y;
while (tail>=1 && x==que[tail][0] && y<que[tail][1]) --tail;
if (tail>0 && que[tail][0]==x && y>=que[tail][1]) return;
while (tail>=2 && cross(node,que[tail],que[tail-1])>=0) --tail;
++tail;que[tail][0]=node[0];que[tail][1]=node[1];
last<?=tail;
}
LL query(LL x)
{
last=tail;
while (last>1 && que[last][0]*x+que[last][1]>que[last-1][0]*x+que[last-1][1])
--last;
return que[last][0]*x+que[last][1];
}
void qsort(LL l,LL r)
{
LL mid=a[(l+r)/2],i=l,j=r;
while (i<j)
{
while (a[i]<mid) ++i;
while (a[j]>mid) --j;
if (i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
++i;--j;
}
}
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}
int main()
{
freopen("HDU3045.in","r",stdin);
freopen("HDU3045.out","w",stdout);
while (scanf("%d%d",&n,&m)!=EOF)
{
for (LL i=0;i<n;++i) scanf("%I64d",&a[i]);
qsort(0,n-1);
for (LL i=n;i>=1;--i) a[i]=a[i-1];a[0]=0;
for (LL i=0;i<=n;++i) sum[i]=0;
for (LL i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
tail=0;last=1;
if (m==0) {printf("0\n");continue;}
for (LL i=m;i<=n;++i)
{
f[i]=sum[i]-i*a[1];
if (i==n)
{
i=n;
}
if (i-m>=m)
{
hulladd(a[i-m+1],f[i-m]-sum[i-m]+(i-m)*a[i-m+1]);
f[i]<?=query(-i)+sum[i];
}
}
printf("%I64d\n",f[n]);
}
return 0;
}
#include<iostream>
#include<cstdio>
#define N 500010
#define LL long long
using namespace std;
LL tail,a[N],que[N][2],sum[N],n,m,last,f[N],i,j,t,T,temp;
LL cross(LL a[2],LL b[2],LL c[2])
{
return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0]);
}
void hulladd(LL x,LL y)
{
LL node[2];
node[0]=x;node[1]=y;
while (tail>=1 && x==que[tail][0] && y<que[tail][1]) --tail;
if (tail>0 && que[tail][0]==x && y>=que[tail][1]) return;
while (tail>=2 && cross(node,que[tail],que[tail-1])>=0) --tail;
++tail;que[tail][0]=node[0];que[tail][1]=node[1];
}
LL query(LL x)
{
last=tail;
while (last>1 && que[last][0]*x+que[last][1]>que[last-1][0]*x+que[last-1][1])
--last;
return que[last][0]*x+que[last][1];
}
void qsort(LL l,LL r)
{
LL mid=a[(l+r)/2],i=l,j=r;
while (i<j)
{
while (a[i]<mid) ++i;
while (a[j]>mid) --j;
if (i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
++i;--j;
}
}
if (i<r) qsort(i,r);
if (l<j) qsort(l,j);
}
int main()
{
freopen("pku3709.in","r",stdin);
freopen("pku3709.out","w",stdout);
scanf("%d",&T);
while (scanf("%d%d",&n,&m)!=EOF)
{
for (LL i=0;i<n;++i) scanf("%I64d",&a[i]);
qsort(0,n-1);
for (LL i=n;i>=1;--i) a[i]=a[i-1];a[0]=0;
for (LL i=0;i<=n;++i) sum[i]=0;
for (LL i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
tail=0;last=1;
if (m==0) {printf("0\n");continue;}
for (LL i=m;i<=n;++i)
{
f[i]=sum[i]-i*a[1];
if (i==n)
{
i=n;
}
if (i-m>=m)
{
hulladd(a[i-m+1],f[i-m]-sum[i-m]+(i-m)*a[i-m+1]);
temp=query(-i)+sum[i];
if (temp<f[i]) f[i]=temp;
}
}
printf("%I64d\n",f[n]);
}
return 0;
}