现在的位置: 首页 > 综合 > 正文

DP优化之斜率优化

2012年03月05日 ⁄ 综合 ⁄ 共 6102字 ⁄ 字号 评论关闭

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之~

HYOJ1010_玩具装箱toy

#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]);
}
pku2018_Best Cow Fences

#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;
}
HDU3045_Picnic Cows

#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;
}
pku3709_K-Anonymous Sequence

#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;
}

抱歉!评论已关闭.