HDU 3507 Print Article(斜率优化推导)

时间:2021-11-08 10:35:18

$dp$,斜率优化。

第一次做斜率优化的题目,看了一些题解,自己总结一下。

这题是说有$n$个数字,可以切成任意段,每一段的费用是这一段数字的和平方加上$M$。问最小费用是多少。

设$dp[i]$为$1$至$i$分段的最小费用,那么$dp[i]=min(dp[j]+M+(sum[i]-sum[j])^2)$。

直接计算的话,时间复杂度是$O(n^2)$,但是这题$n$有$500000$,稳稳的超时。因此,有人想出了斜率优化......

假设有三个位置$a$,$b$,$c$,$a<b<c$。

用$dp[a]$推$dp[c]$:$dp[c]=dp[a]+M+(sum[c]-sum[a])^2$

用$dp[b]$推$dp[c]$:$dp[c]=dp[b]+M+(sum[c]-sum[b])^2$

如果用$b$推$c$比用$a$推$c$要优,即$dp[a]+M+(sum[c]-sum[a])^2>dp[b]+M+(sum[c]-sum[b])^2$。

那么,化简可以得到$[(dp[b]+sum[b]^2)-(dp[a]+sum[a]^2)]/(2*sum[b]-2*sum[a])<sum[c]$。

设$yb=dp[b]+sum[b]^2$,$ya=dp[a]+sum[a]^2$,$xb=2*sum[b]$,$xa=2*sum[a]$。

那么:如果$a<b<c$,且$k[b,a]=(yb-ya)/(xb-xa)<sum[c]$,就可以说 用$b$推$c$比用$a$推$c$要优。

接下来,看一种情况:

设有四个位置:$a<b<c<d$。分别用$a,b,c$位置去推$d$位置。

如果$k[c,b]<k[b,a]$,那么$d$位置的$dp$值绝对不可能从$b$位置推过来。

简单证明如下:

如果$k[b,a]<sum[d]$,也就是说$b$比$a$优,但是$c$比$b$优,所以$b$没用。

如果$k[b,a]>=sum[d]$,也就是说$a$比$b$优,$b$也没用了。

所以在$a<b<c$且$k[c,b]<k[b,a]$的情况下,$b$位置就一定是没用的。

利用上述加红加粗的两个性质,就可以优化这个问题了。需要用一个队列来维护目前还可能往后递推的位置。

计算$dp[i]$的时候,因为队列中相邻两点$x,y$形成的线段的斜率是不断增加的,需要找到第一个不满足$k[y,x]<sum[i]$的$x$,并且$x$之前所有元素均可以从队列中删去,因为$sum[i+1]>sum[i]$,在推$dp[i]$的时候已经用不到那些元素了(被删的元素满足第一条红色性质,都没有$x$优),在推$dp[i+1]$的时候就更加用不到了。

计算得到$dp[i]$之后,可以利用第二条红色性质更新队列,为计算$dp[i+1]$做准备。每次取出队列尾部两个元素和$i$去计算,看是否满足性质$2$,满足的话,队尾就被删了;否则更新结束。

然后计算$dp[i+1]$.......

这样一优化,每个点最多被入队一次,最多出队一次,时间复杂度降到了$O(n)$。

第一次学习斜率优化,感到有一些神奇巧妙,但好像有点难啊......

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<ctime>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c = getchar();
x = ;
while(!isdigit(c)) c = getchar();
while(isdigit(c))
{
x = x * + c - '';
c = getchar();
}
} int n,m;
int q[],dp[], sum[];
int f1,f2; bool check(int a,int b,int c)
{
//ba斜率大于等于sum[c] return 1; 否则 return 0;
if(dp[b]+sum[b]*sum[b]-dp[a]-sum[a]*sum[a]<sum[c]**(sum[b]-sum[a])) return ;
return ;
} bool check2(int a,int b,int c)
{
//bc斜率大于等于ab 则不删b,否则就删b
//cb斜率大于等于ba return 1; 否则 return 0
if((dp[c]+sum[c]*sum[c]-dp[b]-sum[b]*sum[b])**(sum[b]-sum[a])<(dp[b]+sum[b]*sum[b]-dp[a]-sum[a]*sum[a])**(sum[c]-sum[b])) return ;
return ;
} int main()
{
while(~scanf("%d%d",&n,&m))
{
sum[]=; f1=;f2=-; int cnt=; for(int i=;i<=n;i++)
{
int x; scanf("%d",&x);
if(x==) continue;
cnt++;
sum[cnt]=sum[cnt-]+x;
} f2++; q[f2]=; n=cnt; for(int i=;i<=n;i++)
{
while()
{
if(f2-f1+<) break;
if(check(q[f1],q[f1+],i)) break;
f1++;
} dp[i]=dp[q[f1]]+(sum[i]-sum[q[f1]])*(sum[i]-sum[q[f1]])+m; while()
{
if(f2-f1+<) break;
if(check2(q[f2-],q[f2],i)) break;
f2--;
} f2++; q[f2]=i;
} printf("%d\n",dp[n]);
}
return ;
}