首页 > 代码库 > HDU 3507：Print Article
HDU 3507：Print Article
HDU 3507：Print Article
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3507
题目大意：给定$n$，$m$，输出序列$n$个数，每连续输出代价为连续输出的数字和的平方加上$m$.
斜率优化DP
定义$sum_{pq}=\sum_{k=p+1}^qa_k=pre[q]-pre[p]$，其中$pre[]$维护的是前缀和.
直接DP：$dp[i]=min\{dp[q]+sum_{qi}+m\}(q<i)$，如此复杂度为$O(n^2)$，故需要优化.
设$p<q$，若从$q$转移而来比从$p$更优，则有$dp[q]+sum_{qi}+m<dp[p]+sum_{pi}+m$，
化简可得，$\frac{(dp[q]+pre[q]^2)-(dp[p]+pre[p]^2)}{2pre[q]-2pre[p]}<pre[i]$.
令$y(k)=dp[k]+pre[k]^2$，$x(k)=2pre[k]$，
则上式可写为$\frac{y(q)-y(p)}{x(q)-x(p)}<pre[i]$.
其中，$\frac{y(q)-y(p)}{x(q)-x(p)}$可看做斜率，定义$g(p,q)=\frac{y(q)-y(p)}{x(q)-x(p)}$，
故有，若$g(p,q)<pre[i]$，则$q$比$p$更优.
待更...
代码如下：
1 #include <cstdio> 2 #define N 500005 3 using namespace std; 4 typedef long long ll; 5 int n,m,dp[N],a[N],pre[N],deq[N],r,f; 6 int y(int n){return dp[n]+pre[n]*pre[n];} 7 int x(int n){return 2*pre[n];} 8 int main(void){ 9 while(~scanf("%d%d",&n,&m)){10 r=-1,f=0;11 deq[++r]=0;12 for(int i=1;i<=n;++i){13 scanf("%d",&a[i]);14 pre[i]=pre[i-1]+a[i];15 }16 for(int i=1;i<=n;++i){17 while(r-f>0){18 if(y(deq[f+1])-y(deq[f])19 <=pre[i]*(x(deq[f+1])-x(deq[f])))20 f++;21 else break;22 }23 dp[i]=dp[deq[f]]+(pre[i]-pre[deq[f]])*(pre[i]-pre[deq[f]])+m;24 while(r-f>0){25 if((y(deq[r])-y(deq[r-1]))*(x(i)-x(deq[r]))26 >=(y(i)-y(deq[r]))*(x(deq[r])-x(deq[r-1])))27 r--;28 else break;29 }30 deq[++r]=i;31 }32 printf("%d\n",dp[n]);33 }34 }
HDU 3507：Print Article
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。