HDU 3507 Print Article（CDQ分治+分治DP）
forever97
posted @ 2016年9月20日 18:21
in 算法-分治DP
with tags
CDQ分治，分治DP
, 777 阅读
【题目链接】 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;
}
2024年1月18日 16:41
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.