BZOJ 4518 [Sdoi2016]征途（分治DP）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4518
【题目大意】
给出一个数列，分成m段，求方差最小，答案乘上m的平方。
【题解】
化简式子可以发现，就是求将数列分成m段，最小化和的平方和。设dp[i][j]表示处理到第i段，已经用了前j个数的最小代价，我们可以得到dp[i][j]=min(dp[i-1][k]+(s[j]-s[k])2)，由于决策单调，可以分治DP。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <cstdio>typedef long long LL;const int N=3005;int n,m;LL dp[N][N],a[N],s[N],INF=1LL<<60;void DP(int x,int l,int r,int dl,int dr){ int m=(l+r)>>1,i,dm=0; LL *ret=&dp[x][m]; *ret=INF; for(i=dl;i<=dr&&i<m;i++){ LL t=dp[x-1][i]+(s[m]-s[i])*(s[m]-s[i]); if(t<*ret)*ret=t,dm=i; }if(l<m)DP(x,l,m-1,dl,dm); if(r>m)DP(x,m+1,r,dm,dr);}int main(){ 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++)dp[1][i]=s[i]*s[i]; for(int i=2;i<=m;i++)DP(i,1,n,1,n); printf("%lld\n",dp[m][n]*m-s[n]*s[n]);} |
评论 (0)
