本文主要是介绍#单调队列，动态规划，斜率优化#hdu 3507 Print Article，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
一篇文章在打印k个需花费
m是常数，问最少花费多少就可以打完一篇文章
分析
对于 x 1 < x x1<x x1<x and x 2 < x x2<x x2<x
可得 d p [ x ] = d p [ x 1 ] + ( s u m [ x ] − s u m [ x 1 − 1 ] ) 2 + m dp[x]=dp[x1]+(sum[x]-sum[x1-1])^2+m dp[x]=dp[x1]+(sum[x]−sum[x1−1])2+m
d p [ x ] = d p [ x 2 ] + ( s u m [ x ] − s u m [ x 2 − 1 ] ) 2 + m dp[x]=dp[x2]+(sum[x]-sum[x2-1])^2+m dp[x]=dp[x2]+(sum[x]−sum[x2−1])2+m
但是 O ( n 2 ) O(n^2) O(n2)会超时
设 x 1 < x 2 x1<x2 x1<x2 and d p ( x 1 ) < d p ( x 2 ) dp(x1)<dp(x2) dp(x1)<dp(x2)
变形可得
d p [ x 2 ] + s u m [ x 2 − 1 ] 2 − d p [ x 1 ] − s u m [ x 1 − 1 ] 2 2 ( s u m [ x 2 − 1 ] − s u m [ x 1 − 1 ] ) < s u m [ x ] \dfrac{dp[x2]+sum[x2-1]^2-dp[x1]-sum[x1-1]^2}{2(sum[x2-1]-sum[x1-1])}<sum[x] 2(sum[x2−1]−sum[x1−1])dp[x2]+sum[x2−1]2−dp[x1]−sum[x1−1]2<sum[x]
所以如果ANSWER(BC)<=sum[x],证明B点劣于C点，可以去掉B点。否则ANSWER(BC)>sum[x],如果ANSWER(AB)>=ANSWER(BC),则有ANSWER(AB)>sum[x],证明A点优于B点，可去掉B点。所以单调队列维护下凸壳
代码
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
int n,m,q[500001],head,tail; ull sum[500001],f[500001];
ull in(){ull ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
ull print(ull ans){if (ans>9) print(ans/10); putchar(ans%10+48);}
ull up(int i,int j){return f[i]+sum[i]*sum[i]-f[j]-sum[j]*sum[j];}//分子
ull down(int i,int j){return (sum[i]-sum[j])<<1;}//分母
ull dp(int i,int j){return f[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;}//dp的答案
int main(){while (scanf("%d%d",&n,&m)==2){f[0]=q[head=tail=1]=0;for (register int i=1;i<=n;i++){sum[i]=sum[i-1]+in();while (head<tail&&up(q[head+1],q[head])<=sum[i]*down(q[head+1],q[head])) head++;f[i]=dp(i,q[head]);while (head<tail&&up(i,q[tail])*down(q[tail],q[tail-1])<=up(q[tail],q[tail-1])*down(i,q[tail])) tail--;//答案更优q[++tail]=i;} print(f[n]); putchar('\n');}return 0;
}
这篇关于#单调队列，动态规划，斜率优化#hdu 3507 Print Article的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
