Any questions?
Reply Back New Topic
View Topic

斜率优化&&四边形不等式优化算法tips

浏览:431 回复:3 赞:34 Started by ljc20020730 4 months ago

这是斜率优化和四边形优化的所有题目(练习)
请完成并校对所有标准程序已经发至FTP。
大部分内容放至博客(ppt放在FTP上),请按需查看。
https://www.cnblogs.com/ljc20020730/p/10132077.html

斜率优化
P3195 [HNOI2008]玩具装箱TOY
https://www.luogu.org/problemnew/show/P3195
P2120 [ZJOI2007]仓库建设
https://www.luogu.org/problemnew/show/P2120
P3628 [APIO2010]特别行动队
https://www.luogu.org/problemnew/show/P3628
BZOJ 2726: [SDOI2012]任务安排
https://www.lydsy.com/JudgeOnline/problem.php?id=2726
P4027 [NOI2007]货币兑换
https://www.luogu.org/problemnew/show/P4027

四边形优化
结论:
1.四边形不等式的定义:相交小于包含
两种等价定义:
对于a<=b<=c<=d属于Z,都有w(a,d)+w(b,c)>=w(a,c)+w(b,d)
对于a,b属于Z 若 a<b,有w(a,b+1)+w(a+1,b)>=w(a,b)+w(a+1,b+1)
2.一维线性DP决策单调定理
对于形如f[i]=min_{0<=j<i}{F[j]+w(j,i)}若w为凸那么F决策单调递增
3.二维区间DP决策单调性定理
对于形如Fi=min_{i<=k<=j}{fi+fk+1+w(i,j)}
(特别的要求Fi=w(i,i)=0) 若w为凸则F为凸,
对于F理应满足决策Pi<Pi<Pi+1
Pl表示当l,r]分为[l,k]和[k+1,r]两部分时F[l最大

利用第二种等价定义,证明函数w(x,y)的凸性事实上只要
证明对于任意j<i,w(j,i+1)+w(j+1,i)>=w(j,i)+w(j+1,i+1)
只需证明:w(j+1,i)-w(j+1,i+1)>=w(j,i)-w(j,i+1)
代入换元函数单调性可知w(x,y)的凸性

更方便的方案:打表暴力DP验证决策单调!

P1912 [NOI2009]诗人小G
https://www.luogu.org/problemnew/show/P1912
U58387 石子合并(弱化版本)
https://www.luogu.org/problemnew/show/U58387
U58393 石子合并(强化版本)
https://www.luogu.org/problemnew/show/U58393
P4767 [IOI2000]邮局
https://www.luogu.org/problemnew/show/P4767

View Replies

Replied by ljc20020730 4 months ago 赞:6

斜率优化部分推荐题目

BZOJ 1597: [Usaco2008 Mar]土地购买
https://www.lydsy.com/JudgeOnline/problem.php?id=1597
BZOJ 3156: 防御准备
https://www.lydsy.com/JudgeOnline/problem.php?id=3156
BZOJ 3675: [Apio2014]序列分割
https://www.lydsy.com/JudgeOnline/problem.php?id=3675
BZOJ 3156: 防御准备
https://www.lydsy.com/JudgeOnline/problem.php?id=4518


Replied by ljc20020730 2 weeks ago 赞:0

inline int read()
{

int X=0,w=0; char c=0;
while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
return w?-X:X;

}
inline void write(int x)
{

if (x>9) write(x/10);
putchar('0'+x%10);

}


Replied by ljc20020730 2 weeks ago 赞:0
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}
inline void write(int x)
{
    if (x>9) write(x/10);
    putchar('0'+x%10);
}