首页 > 代码库 > HDU 3507 Print Article（CDQ分治+分治DP）
HDU 3507 Print Article（CDQ分治+分治DP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=3507
【题目大意】
将长度为n的数列分段，最小化每段和的平方和。
【题解】
根据题目很容易得到dp[j]=min(dp[k]+(s[j]-s[k])2)，因为是从前往后转移，且决策单调，因此在CDQ分治的同时进行分治DP即可。
【代码】
#include <cstdio>typedef long long LL;const int N=500005;int n,M,t;LL f[N],g[N],a[N],s[N],INF=1LL<<60;void DP(int l,int r,int dl,int dr){ int m=(l+r)>>1,i,dm=0; LL &ret=g[m]; ret=INF; for(i=dl;i<=dr&&i<m;i++){ LL t=f[i]+(s[m]-s[i])*(s[m]-s[i])+M; if(t<ret)ret=t,dm=i; }if(l<m)DP(l,m-1,dl,dm); if(r>m)DP(m+1,r,dm,dr);}void CDQ(int l,int r){ if(l==r)return; int mid=(l+r)>>1; CDQ(l,mid); DP(mid+1,r,l,mid); for(int i=r;i>mid;i--)if(g[i]<f[i])f[i]=g[i]; CDQ(mid+1,r);}int main(){ while(~scanf("%d%d",&n,&M)){ for(int i=1;i<=n;i++){scanf("%lld",&s[i]);s[i]+=s[i-1];} for(int i=1;i<=n;i++)f[i]=s[i]*s[i]+M;CDQ(0,n); printf("%lld\n",f[n]); }return 0;}
HDU 3507 Print Article（CDQ分治+分治DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。