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。
【代码】
#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)
