这道题化简以后就是要求把一个环分成K份，值得每份的平方之和最小； 这个的O(n^3m)的DP显然， 发现DP时几乎符合决策单调性，（不是全部） 所以可以用一个水法， 当然也可以用斜率优化， 还有一个分治的做法，因为每轮选的位置都是在上一次选的后面， 所以二分一个点，暴力找到它的最优位置，再把当前的区间分治下去， 复杂度多一个log，
这个是水法
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)#define sqr(q) ((q)*(q))#define ZHI(t) (sqr(sum[t]-sum[L-1])+sqr(sum[R]-sum[t]))using namespace std;typedef long long LL;const int N=605005;int read(int &n){ char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;}int n,K;LL ans,P;int a[N];LL f[1000][55],sum[N];void ss(int q){ int mi; memset(f,127,sizeof(f)); f[q-1][0]=0; fo(i,q,n+q-1)f[i][1]=sqr(sum[i]-sum[q-1]); fo(j,1,K-1) { mi=q-1+j; fo(i,q+j,n+q-1) { fo(k,mi,i-1) { if(f[i][j+1]>f[k][j]+sqr(sum[i]-sum[k]))mi=k; else break; f[i][j+1]=min(f[i][j+1],f[k][j]+sqr(sum[i]-sum[k])); } } }}LL sf(int L,int R){ int l=L,r=R; while(l+1<r) { int t=l+(r-l+1)/3,t1=l+(r-l+1)/3*2; if(ZHI(t)>ZHI(t1))l=t+1; else if(ZHI(t)<ZHI(t1))r=t1-1; else l=t,r=t1; } return (ZHI(l)<ZHI(r))?ZHI(l):ZHI(r);}int MV(int q,LL w,LL e){ fo(i,q,n*2)if(w<=sum[i]-e)return i; return n*2;}int main(){ read(n),read(K); fo(i,1,n)P+=(a[i+n]=read(a[i])); fo(i,1,n*2)sum[i]=sum[i-1]+a[i]; ans=1e16; LL q=P*P*K-2*K*P*P; if(K==3) { LL t=sum[n]/3; int l=0,r=0; fo(i,1,n) { l=MV(l,t,sum[i-1]); r=MV(r,t*2,sum[i-1]); fo(j,max(1,l-3),min(i+n-1,l+3))fo(k,max(1,r-3),min(i+n-1,r+3)) ans=min(ans,sqr(sum[j]-sum[i-1])+sqr(sum[k]-sum[j])+sqr(sum[i+n-1]-sum[k])); } PRintf("%lld/n",ans*K*K+q); return 0; } if(K==2) { fo(i,1,n) ans=min(ans,sf(i,n+i-1)); printf("%lld/n",ans*K*K+q); return 0; } fo(i,1,n) { ss(i); ans=min(ans,q+(LL)f[n+i-1][K]*K*K); } printf("%lld/n",ans); return 0;}新闻热点
疑难解答
